The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы
правила/FAQ
поиск
регистрация
вход
слежка
RSS


Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

Релиз языка программирования Go 1.10, opennews (??), 18-Фев-18, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


33. "Релиз языка программирования Go 1.10"  +2 +/–
Сообщение от Аноним (-), 18-Фев-18, 16:45 
>простой в понимании код

Из https://stackoverflow.com/questions/21326109/why-are-lists-u...
мы можем узнать, что вместо списков в Go следует использовать слайсы с таким замечательным синтаксисом:

Delete:

a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])]

Delete without preserving order:

a[i], a = a[len(a)-1], a[:len(a)-1]

Pop:

x, a = a[len(a)-1], a[:len(a)-1]

Ответить | Правка | Наверх | Cообщить модератору

74. "Релиз языка программирования Go 1.10"  +3 +/–
Сообщение от angra (ok), 18-Фев-18, 20:57 
И что же здесь не так? Автоматичекое управление памятью в Go существует вовсе не для того, что бы программист вообще не понимал, как идет работа с памятью. Наоборот, детали реализации массивов, срезов, списков, отображений совсем не скрываются и их понимание приветствуется.
Представленый код очень даже простой, если ты все-таки ознакомился с тем, как работают срезы. Если очень хочется, то программист может написать однострочные функции обертки для таких "высокоуровневых" операций как delete и pop.
Ответить | Правка | Наверх | Cообщить модератору

88. "Релиз языка программирования Go 1.10"  +3 +/–
Сообщение от Orduemail (ok), 19-Фев-18, 00:52 
> вместо списков в Go следует использовать слайсы с таким замечательным синтаксисом

Да, это превосходная иллюстрация к тому, что значит простой код. Особенно если сравнить это с удалением из массива в C, где придётся использовать memove и realloc для того же, или даже если мы в C забьём на скорость, и будем использовать список, где придётся десятку указателей менять значения, обрабатывая при этом всякие специальные случаи, то этот код -- просто эталон простоты.
В том же rust'е, как и в C, удаление элемента из массива/слайса -- это настолько геморройная операция, что она вынесена в специальную функцию.

Ответить | Правка | К родителю #33 | Наверх | Cообщить модератору

93. "Релиз языка программирования Go 1.10"  +1 +/–
Сообщение от angra (ok), 19-Фев-18, 02:46 
> даже если мы в C забьём на скорость, и будем использовать список, где придётся десятку  указателей менять значения, обрабатывая при этом всякие специальные случаи.

Зачем? Для обоих случаев в односвязном списке достаточно изменить ровно один указатель. И делается это вполне элегантно. Опять таки скорость самого удаления в случае списков выше, а не ниже. У них проблема со скоростью на совсем других операциях, например на поиске элемента для удаления. Сдается мне, тебе стоит повторить теорию.

Ответить | Правка | Наверх | Cообщить модератору

94. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Stop (?), 19-Фев-18, 04:21 
Подмена понятий "массив" и "список". Срочно учить теорию.
Ответить | Правка | Наверх | Cообщить модератору

97. "Релиз языка программирования Go 1.10"  +1 +/–
Сообщение от angra (ok), 19-Фев-18, 06:02 
Ты не способен проследить дискуссию длиной в целых три поста? Никто ничего не подменял.
Ответить | Правка | Наверх | Cообщить модератору

98. "Релиз языка программирования Go 1.10"  +2 +/–
Сообщение от Orduemail (ok), 19-Фев-18, 06:39 
>> даже если мы в C забьём на скорость, и будем использовать список, где придётся десятку  указателей менять значения, обрабатывая при этом всякие специальные случаи.
> Зачем? Для обоих случаев в односвязном списке достаточно изменить ровно один указатель.
> И делается это вполне элегантно.

Угу, менять надо один указатель и это можно сделать элегантно, но при выполнении ряда условий:
- список _односвязный_, а односвязные списки неудобны, потому что для удаления элемента надо либо иметь указатель на предыдущий элемент, либо перемещать содержимое следующего элемента в этот, что уже неэлегантно и не один указатель, да ещё и не работает с последним элементом
- удаляемый элемент выкидывается, и поэтому не требуется в нём менять значения указателей на что-нибудь типа NULL, во избежание возможных трудноотлавливаемых багов с "висячими" указателями
- список организован не "в лоб", а несколько хитрее, чтобы специальный случай удаления первого элемента не требовал бы специальных телодвижений -- например, это список с заголовком

Кстати я не уверен, что эти условия совместимы, что действительно можно придумать односвязный список (в котором достаточно поменять ровно один указатель), с которым не придётся обрабатывать краевых случаев. Двусвязный циклический с заголовком достаточно красивым получается, но там большинство операций -- это изменение четырёх указателей. Плюс подчастую приходится трогать три списочных ячейки, случайным образом разбросанные по памяти, а это потенциально три кеш-промаха.

> Опять таки скорость самого удаления в
> случае списков выше, а не ниже. У них проблема со скоростью
> на совсем других операциях, например на поиске элемента для удаления. Сдается
> мне, тебе стоит повторить теорию.

А что теория? Теория говорит о каких-то абстракциях, типа O(1) или O(n). То есть всё что она говорит, это то, что существует такое N, что при всех n>N удаление элемента из массива окажется медленнее, чем удаление из списка. И чё мне с того? При каком N такое случится? Теория отказывается отвечать на эти вопросы, а зря. Ведь если, допустим, это случается при N=10000, то подавляющее большинство моих контейнеров будет удалять элементы быстрее, если я буду использовать массивы, потому что я довольно редко использую массивы из десятков тысяч элементов и больше.

Списки -- это всегда кеш-промахи в промышленных количествах. А раз кеш-промахи, значит алгоритм в целом начинает упираться в скорость доступа к DRAM, а эта скорость никакая. Она десятилетиями наращивает отставание от скорости процессоров. И не видно признаков тому, что этот тренд сломается в обозримом будущем. Насколько я понимаю этот вопрос -- скорость доступа к памяти зависит от размера этой памяти (я подозреваю, что там логарифмическая зависимость), объёмы памяти постоянно наращиваются, и если мы не получаем замедления DRAM с годами, то лишь благодаря самоотверженному труду разработчиков микросхем памяти. Но если мы не получаем _абсолютного_ замедления, то _относительное_ (в сравнении с процессором) тем не менее имеет место.

Процессоры заточены на работу с массивами, а вот рандом-акцесс им даётся сложно, и при таких раскладах, теоретический O(1) может быть медленнее, чем практический O(n). А если мы ещё вспомним, что при удалении элемента из списка надо не забыть скормить освобождённую списочную ячейку в функцию free, то есть дёрнуть тормозную кучу и её структуры данных, то легко может выйти, что O(n) времени на memmove килобайта памяти, вызванный удалением элемента из массива, займёт меньше времени, чем O(1) на удаление элемента из списка.

Ответить | Правка | К родителю #93 | Наверх | Cообщить модератору

102. "Релиз языка программирования Go 1.10"  +1 +/–
Сообщение от angra (ok), 19-Фев-18, 10:06 
Последую совету одного финского парня "Talk is cheap. Show me the code".

Односвязный список https://play.golang.org/p/rBDrCbJ9zUi
Собственно удаление занимает одну строчку и состоит в изменении одного указателя, место выделено комментарием. Удаление головы также занимает одну строчку и состоит в возвращении указателя на следующий элемент. Никакой специальной обработки последнего элемента, никаких перемещений значений. Никаких апдейтов десятка указателей и прочей чуши.

Двусвязный список https://play.golang.org/p/pl7FOfdiUDb
Удаление даже выделено в отдельную функцию, которая принимает только удаляемый элемент. Состоит в апдейте максимум двух указателей. Не четырех, нет

Ответить | Правка | Наверх | Cообщить модератору

137. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 20-Фев-18, 03:00 
Хых. Мы ушли от общей идеи удаления элемента в вакууме к частому случаю в конкретном контексте. Я не к тому, что я против, я лишь хочу отметить этот момент, для ясности.


Вот фильтрация на C. Я Go не знаю и ставить его мне лень, а синтаксически неверное подражание ему писать не охота, поэтому на C. Но это детали и не важно.

struct Vec {
    size_t len;
    int *buf;
};

void filter(int val, struct Vec *vec) {
    size_t write = 0;
    for(size_t read = 0; read < vec.len; read ++) {
        if(vec.buf[read] != val) {
            vec.buf[write++] = vec.buf[read];
        }
    }
    vec.len = write;
}

Тут виден чёткий последовательный доступ к памяти, который очень хорошо ложиться на стратегии кеширования процессора, и мы видим, что это короче. Код со списками содержит практически такой же цикл, и я не вижу никаких существенных различий между этими циклами *с точки зрения*, простоты как основы *читабельности и возможности поддерживать код*. Но мы видим, что в случае списков, перед циклом и после цикла возникает та самая обработка краевых условий, о которых я говорил.

Ответить | Правка | Наверх | Cообщить модератору

138. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 20-Фев-18, 03:18 
>[оверквотинг удален]
>  }
>  vec.len = write;
> }
> Тут виден чёткий последовательный доступ к памяти, который очень хорошо ложиться на
> стратегии кеширования процессора, и мы видим, что это короче. Код со
> списками содержит практически такой же цикл, и я не вижу никаких
> существенных различий между этими циклами *с точки зрения*, простоты как основы
> *читабельности и возможности поддерживать код*. Но мы видим, что в случае
> списков, перед циклом и после цикла возникает та самая обработка краевых
> условий, о которых я говорил.

[add]
> Состоит в апдейте максимум двух указателей. Не четырех, нет...

Угу. Но это потому что списочная ячейка после удаления перестаёт существовать, отправляясь в свободную память в куче. Это очень часто не так, когда используется список с принудительной связью, чтобы снизить количество мелких аллокаций в куче (хотя это, я думаю, менее релевантно для языков со сборкой мусора, потому что им не надо вызывать free на каждую освобождаемую ячейку, плюс дефрагментация кучи тотальна и условно бесплатна). И в этом случае списочная ячейка продолжит существовать, но в "плохом" состоянии: она будет выглядеть как валидная списочная ячейка включённая в список. Поэтому её указатели стоит отресетить в NULL, или на саму себя (в зависимости от тонкостей реализации списков), а это удваивает количество изменяемых указателей при операциях удаления и приравнивает его к количеству изменяемых указателей в случае вставки. Это вряд ли существенно влияет на производительность, которая в любом случае упрётся в скорость DRAM, но код захламляет. Что опять же не очень важно, поскольку эти вещи всё равно выносятся в inline-функции, но разговор ведь начался с того, что синтаксис слайсов слишком заморочен, и вроде как списки выглядят лучше.

Ответить | Правка | Наверх | Cообщить модератору

142. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 20-Фев-18, 06:42 
У тебя тоже проблемы с отслеживанием дискуссии на три поста? Вернись и почитай, что именно я оспаривал, а с чем молча согласился. Потом подумай, как написанное тобой относится к моим возражениям. В чем ты сейчас меня пробуешь убедить, мне совершенно непонятно.

Отдельно отмечу, что перед циклом я обрабатываю не краевой случай, а условие передачи нулевого указателя и мой код отработает в этом случае корректно, а твой свалится с сегфолтом. Еще веселее, что при всех заумных разговорах о стратегиях кеширования процессора, твоя реализация будет вынуждена при добавлении элемента каждый раз заново выделять память на весь массив и осуществлять его полное копирование, ведь ты забыл предусмотреть хранение размера выделенного буфера в отдельном поле.

Ответить | Правка | К родителю #137 | Наверх | Cообщить модератору

144. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 20-Фев-18, 08:14 
> У тебя тоже проблемы с отслеживанием дискуссии на три поста?

Естественно. Ты мечешься между "списки быстрее массивов" и "списки писать проще чем массивы", сложно отследить, что именно тебя волнует в данный момент больше. Поэтому, на всякий случай, лучше бить по площадям.

> Вернись и
> почитай, что именно я оспаривал, а с чем молча согласился. Потом
> подумай, как написанное тобой относится к моим возражениям. В чем ты
> сейчас меня пробуешь убедить, мне совершенно непонятно.

В том, что а) синтаксис слайсов из Go -- это превосходный и лаконичный синтаксис для работы со "списками", в смысле с контейнерами-последовательностями; б) там где есть такой синтаксис, связные списки не нужны. Причём не нужны не только в стандартной библиотеке, но и в качестве наколенной реализации.

> Отдельно отмечу, что перед циклом я обрабатываю не краевой случай, а условие
> передачи нулевого указателя и мой код отработает в этом случае корректно,
> а твой свалится с сегфолтом.

В мой код не будет передан нулевой указатель, в этом нет никакой нужды. Там есть поле len, которого более чем достаточно для того, чтобы функция filter не выходила бы за рамки safe поведения.

> Еще веселее, что при всех заумных
> разговорах о стратегиях кеширования процессора, твоя реализация будет вынуждена при добавлении
> элемента каждый раз заново выделять память на весь массив и осуществлять
> его полное копирование, ведь ты забыл предусмотреть хранение размера выделенного буфера
> в отдельном поле.

Мой код, если ты не заметил, не добавляет элементов. В нём даже не реализована неспецифическая операция удаления элемента, есть лишь функция filter, которая де факто элементы удаляет, но специфическим образом. Так что кто из нас "заумнее" -- это ещё посмотреть надо.

Ответить | Правка | Наверх | Cообщить модератору

146. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 20-Фев-18, 17:05 
Понятно, разговариваешь с голосами в голове, ну или со всеми в этом треде сразу, не различая, кто что говорил. В любом случае не буду мешать.
Где именно упадет твой код, ты так и не понял, а ведь там всего несколько строк. Зато умные слова про кеши процессора знаешь. Молодец, начальство таких любит.
Ответить | Правка | Наверх | Cообщить модератору

147. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 20-Фев-18, 21:02 
> Понятно, разговариваешь с голосами в голове, ну или со всеми в этом треде сразу, не различая, кто что говорил.

Ты всегда, когда у тебя заканчиваются аргументы, переходишь на обсуждение личностей? Ты с самого начала пытался сделать это -- я выше перечислял, основные направления твоих высказываний, и умолчал про то, что ты с самого начала не мог и двух предложений написать на техническую тему, не внедрив в них каких-нибудь своих идей о личностных свойствах собеседника. Но здесь, как-то, ты совсем ушёл от технических аргументов.

Ответить | Правка | Наверх | Cообщить модератору

152. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 21-Фев-18, 03:59 
Цитирую себя: "Зачем? Для обоих случаев в односвязном списке достаточно изменить ровно один указатель. И делается это вполне элегантно. Опять таки скорость самого удаления в случае списков выше, а не ниже. У них проблема со скоростью на совсем других операциях, например на поиске элемента для удаления. Сдается мне, тебе стоит повторить теорию."

Это ВСЁ, что я написал тебе на тему списков. Когда ты с этим не согласился и начал толкать речи про кеши, я подтвердил свои слова кодом. Без каких либо переходов на личности, которые ты себе навоображал. Дальше ты начал разговаривать с голосами в голове и доказывать им неизвестно что. Им, не мне. Так как я не знаю, что они тебя шепчут и на что ты отвечаешь. Какие в этом случае вообще могут быть аргументы с моей стороны? Разве что прокомментировал огрехи в твоем коде, который непонятно что должен был продемонстрировать. Если с твоей точки зрения это уход от технических аргументов, то я уж не знаю, что ты будешь считать таковыми. Наверное только безоговорочное соглашение с твоей ахинеей про апдейт десятка указателей.

Ответить | Правка | Наверх | Cообщить модератору

153. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 21-Фев-18, 04:56 
> Цитирую себя: "Зачем? Для обоих случаев в односвязном списке достаточно изменить ровно
> один указатель. И делается это вполне элегантно. Опять таки скорость самого
> удаления в случае списков выше, а не ниже. У них проблема
> со скоростью на совсем других операциях, например на поиске элемента для
> удаления. Сдается мне, тебе стоит повторить теорию."
> "Сдается мне, тебе стоит повторить теорию."
> "Без каких либо переходов на личности, которые ты себе навоображал."

=)
Не, ты действительно думаешь, что обсуждение того, что мне следует повторить -- это обсуждение технических проблем, а не моей личности?

Ответить | Правка | К родителю #152 | Наверх | Cообщить модератору

155. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 21-Фев-18, 22:06 
Я тебя наверное сейчас очень удивлю, но таки это не имело вообще никакого отношения к твоей личности.
Но зато сейчас я с удовольствием перейду на личности и сообщу, что твоя личность в некоторых аспектах имеет развитие моего 4-летнего сына. Он тоже, когда ему указываешь на объективные недостатки в его поведении, например раскидал и не собрал игрушки, вместо их ликвидации устраивает нытье на тему "меня обидели". Шестилетний сын уже так себя не ведет, перерос.
Ответить | Правка | К родителю #153 | Наверх | Cообщить модератору

156. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 22-Фев-18, 01:28 
> Я тебя наверное сейчас очень удивлю, но таки это не имело вообще
> никакого отношения к твоей личности.

Люди превосходно умеют видеть себя именно такими, какими хотят. А хотят они себя видеть белыми и пушистыми, поэтому даже когда они совершают гадости, они уверены, что они поступили хорошо и правильно. А если и не хорошо, то у них всегда наготове десяток оправданий своему поведению. Люди умеют вытеснять, и видеть в своём поведении только те аспекты, которые им хочется видеть. Так что нет, то что ты не видишь в своих словах перехода на личности, никоим образом не может меня удивить.

> Но зато сейчас я с удовольствием перейду на личности и сообщу, что
> твоя личность в некоторых аспектах имеет развитие моего 4-летнего сына. Он
> тоже, когда ему указываешь на объективные недостатки в его поведении, например
> раскидал и не собрал игрушки, вместо их ликвидации устраивает нытье на
> тему "меня обидели".

Если ты указываешь на недостатки поведения своего сына в том же стиле, как и в этом разговоре ты указываешь мне, то в этом нет ничего удивительного. Более того, потенциально ты создаёшь своему сыну кучу психологических проблем, с которыми ему придётся жить всю его оставшуюся жизнь.
Если ты хочешь говорить о недостатках поведения в настоящем, то надо говорить о недостатках поведения в настоящем, а не о недостатках личности, которые привели к этому поведению, и не о мерах, которые человеку следует предпринять, чтобы исправить эти недостатки личности.
Если ты будешь говорить ребёнку о недостатках личности, или даже не о недостатках, а вообще о свойствах личности, ребёнок начнёт считать эти свойства своим неотъемлимым свойством.
Если это непонятно в абстрактном изложении, то представь себе ребёнка, которому один сказали "жадина какая, с братом не хочет делиться", и который когда к нему в следующий раз докопались с идеей поделиться, ответил "естественно я не поделился, я же жадина". Ещё интереснее, если замечания касаются интеллекта -- я вижу вокруг себя множество людей, которые даже не пытаются применять интеллект, потому что заранее уверены, что у них ничего не получится. И я уверен, что в большинстве случаев, им благодарить за это надо родителей. Ну и наконец, если ты своими сообщениями транслируешь ребёнку общие идеи о том, что он плохой (ну или, что его поведение -- это признак "плохости", ребёнку без разницы), то результатом будет ребёнок с самооценкой, которая разрушена в целом, а не в отдельных аспектах.

И я бы посоветовал, начав с того, чтобы научиться видеть переход на личности в своей речи, затем совершить ещё один шаг в развитии своей речи, и освоить "Я-сообщения" и говорить не о _объективных_ недостатках поведения, а о субъективных -- не "ты ведёшь себя плохо", а "мне не нравится, когда ты делаешь так-то и так-то". То есть, говорить даже не о свойствах поведения, а о своих чувствах в отношении этого поведения. Почему это полезно можно очень долго говорить, там много интересных последствий, но я не буду этого делать, именно потому, что это долго. Но ты можешь взять и почитать, что-нибудь. Я понимаю, с этим проблема, потому что совершенно неграмотной около-психологической писанины в интернете на порядок больше, чем осмысленных вещей, но вот смотри, это список литературы, которую нам кидали к зачёту по семейной психологии:
Петрановская. Тайна опора: привязанность в жизни ребёнка.
Млодик. Как быть неидеальными родителями.
Гиппенрейтер. Общаться с ребёнком. Как.
Гиппенрейтер. Продолжаем общаться с ребёнком.

Эти книжки написаны психологами для не-психологов. Имеет смысл прочесть все, но если ты считаешь, что во фразе "тебе следовало бы повторить теорию" нет перехода на личности, то, мне кажется, что Гиппенрейтер будет наиболее полезной. Я сам не читал её, но насколько я помню обсуждение книжки на семинаре, это довольно грамотно написанная книжка, плюс с Гиппенрейтер я сталкивался по другим вопросам, и считаю, что звание "доктор психологических наук" более чем заслужено ею. И, насколько я помню, там написано как раз то, что нужно тебе, чтобы осознать, что именно ты говоришь, когда открываешь рот.

Мне ты можешь говорить как тебе угодно, и что тебе угодно -- я в достаточной степени сформировавшаяся личность, чтобы пропускать любые твои замечания о моей личности через фильтры психологических защит, ребёнок же ещё не имеет таких возможностей. И если ребёнок обижается на твои слова, значит _ты_его_обижаешь_. Особенно если мы говорим о ребёнке 6 лет, который ещё не утратил детскую непосредственность. Он пока лишь подошёл к возрасту утраты её.

> Шестилетний сын уже так себя не ведет, перерос.

Или может не просто подошёл, а прошёл через эту утрату. Или может ты, к его шести годам, научился говорить ему об "объективных" недостатках поведения, как о субъективных. Или не как о субъективных, но не в обидном ключе. Или, что скорее (и хуже), он адаптировался: дети учатся быстрее родителей.

Ответить | Правка | К родителю #155 | Наверх | Cообщить модератору

158. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 22-Фев-18, 06:25 
Ты серьезно думаешь, что кто-то будет слушать советы по воспитанию детей от человека, чье психологическое развитие в отдельном аспекте уступает нормальному шестилетнему ребенку? Тут мне остается только повторить известное высказывание:"папе своему советы давай, если он у тебя конечно есть" и попрощаться.

P.S. Ошибку в своем коде ты хотя бы нашел? Вопрос риторический.

Ответить | Правка | К родителю #156 | Наверх | Cообщить модератору

159. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 22-Фев-18, 06:43 
> Ты серьезно думаешь, что кто-то будет слушать советы по воспитанию детей от
> человека, чье психологическое развитие в отдельном аспекте уступает нормальному шестилетнему
> ребенку? Тут мне остается только повторить известное высказывание:"папе своему советы
> давай, если он у тебя конечно есть" и попрощаться.

Ну, что я могу на это сказать? Посочувствовать ребёнку, имеющему такого отца? Я тебе дал список литературы -- если ты не веришь моим советам, читай советы специалистов. Не хочешь читать, ну так будь мужиком, признайся себе в этом честно, и не придумывай себе оправданий, сваливая ответственность за эти решения на уровень моего развития.

> P.S. Ошибку в своем коде ты хотя бы нашел? Вопрос риторический.

Нашёл, но я уверен, что это не та ошибка, о которой ты говоришь. У меня есть подозрения, о чём ты говоришь, но это настолько глупо, что я не хочу даже говорить об этом, чтобы нечаянно не обидеть тебя: вдруг я ошибаюсь и ты о чём-то другом, не столь глупом?

Ответить | Правка | К родителю #158 | Наверх | Cообщить модератору

112. "Релиз языка программирования Go 1.10"  –1 +/–
Сообщение от Аноним (-), 19-Фев-18, 13:54 
> скорость самого удаления в
> случае списков выше, а не ниже.

Ну-ка, рассчитай нам скорость удаления последнего элемента из массива и из односвязного списка размером 100 элементов.

Ответить | Правка | К родителю #93 | Наверх | Cообщить модератору

126. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 19-Фев-18, 18:41 
А если массив/список на пару десятков тысяч элементов длиной в сотню байт каждый и надо удалить не первый или последний, а что-то в средине?
Ответить | Правка | Наверх | Cообщить модератору

128. "Релиз языка программирования Go 1.10"  +/–
Сообщение от анон (?), 19-Фев-18, 20:45 
Так мы медленно пришли к проблеме выбора корректного контейнера. В Go вам всего хеш-таблица, и массив со слайсом.
Ответить | Правка | Наверх | Cообщить модератору

131. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 19-Фев-18, 21:11 
Ну если для тебя использовать стандартную либу западло, а написать реализацию связного списка самому является слишком сложной задачей, то наверное в Go тебе еще рано. Поищи себе ЯП в котором связные списки есть на уровне языка. Интересно, есть ли такой вообще.
Ответить | Правка | Наверх | Cообщить модератору

132. "Релиз языка программирования Go 1.10"  –2 +/–
Сообщение от анон (?), 19-Фев-18, 21:37 
C++?
Java?
C#?
Я должен писать список под каждый тип, или через interface{} сделать?
Go generate не предлагаете?
На экзамене валить не будете?
Ответить | Правка | Наверх | Cообщить модератору

133. "Релиз языка программирования Go 1.10"  –1 +/–
Сообщение от анон (?), 19-Фев-18, 21:39 
> C++?
> Java?
> C#?
> Я должен писать список под каждый тип, или через interface{} сделать?
> Go generate не предлагаете?
> На экзамене валить не будете?

Ох, сорян. На уровне языка. На уровне языка у меня инструментов, чтобы не городить в стандартной и в сторонней либе кучу костылей, завязанных на рантайм и тайп ассерты

Ответить | Правка | Наверх | Cообщить модератору

135. "Релиз языка программирования Go 1.10"  +/–
Сообщение от angra (ok), 19-Фев-18, 23:30 
> Ох, сорян. На уровне языка.

Заметь, это не я первым предложил.

> Я должен писать список под каждый тип, или через interface{} сделать?

В зависимости от задачи. Причем само собой писать под каждый тип вручную не нужно, достаточно общий шаблон. Еще ты почему-то забыл самый практически применимый вариант - писать под конкретный интерфейсный тип.

> На уровне языка у меня инструментов, чтобы  не городить в стандартной и в сторонней либе кучу костылей, завязанных на рантайм и тайп ассерты

И в go они тоже есть.

> Go generate не предлагаете?

Почему нет? Именно его и предлагаю, тем более, что он решает более широкий класс задач, чем дженерики.

Ответить | Правка | Наверх | Cообщить модератору

139. "Релиз языка программирования Go 1.10"  +/–
Сообщение от Orduemail (ok), 20-Фев-18, 03:49 
> Ну если для тебя использовать стандартную либу западло, а написать реализацию связного
> списка самому является слишком сложной задачей, то наверное в Go тебе
> еще рано. Поищи себе ЯП в котором связные списки есть на
> уровне языка. Интересно, есть ли такой вообще.

Это есть в LISP. Но ни в лиспе, ни где-либо ещё я не буду создавать список из 10k элементов. Если так уж всё упирается во вставки и удаления, то напрашиваются оптимизации массива, а не список из 10k элементов.

Во-первых, можно пересмотреть алгоритм, которому нужно вставлять и удалять, и что-нибудь в нём поменять, с тем чтобы либо не надо было бы вставлять/удалять, либо чтобы при вставках/удалениях можно было бы игнорировать порядок элементов. Во-вторых, операции вставки и удаления можно выполнять батчами по нескольку штук. В-третьих, на крайняк, можно создать что-то a la gap-buffer'а, имеющего N gap'ов, что, в среднем, поделит время вставки/удаления на N (если N на два-три порядка меньше 10000), ценой увеличения времени рандом-акцесса с O(1) до O(log(N)).

Первые две альтернативы, кстати, вполне себе объединяются в одну: если совсем отказаться от упорядоченности нельзя, то элементы можно вставлять в конец массива, удалять их можно тоже с конца массива, предварительно переместив их туда операцией swap. А перед операциями требующими упорядоченности выполнять сортировку массива каким-нибудь алгоритмом, заточенным на сортировку "почти отсортированных" массивов, который будут давать "почти линейное" время сортировки. Или их можно не объединять, но придумать свой lazy-"процессор" вставок/удалений, который получая запросы на вставки/удаления будет лишь записывать, что надо сделать, но ничего не делать, а когда придёт время, он возьмёт список вставок/удалений, оптимизирует его, переупорядочив их так как ему удобнее и выполнит одним проходом по массиву. Это будет гораздо сложнее, чем push+swap_remove+sort (что минус с точки зрения возможности дальнейшей поддержки кода), и не факт, что даст выигрыш по скорости, но если заняться нечем и хочется реализовать свой контейнер, то отличная практика для скиллов составления алгоритмов.

Если вставка/удаление в случайные места массива тормозит, и требуется оптимизация, то замена массива на список -- это не оптимизация, а жест отчаяния. Если же массив не тормозит, то тем более не стоит заменять его на список. В lisp'е можно создать список вместо массива, но только если этот список достаточно мелкий, и если это происходит в коде, производительность которого нас не колышет, и это в lisp'е, просто потому что в нём очень удобно работать со списками, гораздо удобнее чем с массивами.

Ответить | Правка | К родителю #131 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей 		Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру