Comments 32
интерпретаторы это тоже жульничество по вашим же критериям. это vm, а не конкретное устройство и все вычислительные ресурсы это ресурсы обслуживания вирт машины.
Рассмотрим следующий код:
Node* root = make_circular_linked_list(...);Node* cur = root;while (true) { cur = cur->next;}
забавно, но я в своих решениях часто пользуюсь такими списками и очени быстрые, особенно если вам не нужен доступ по индексу. Я пишу на C# и вместо List делаю такие вот списки и они получаются быстрее.
Например на Highload.fun есть задача Order Book, я её делал через List (это динамический массив), а потом переделал на свой двухсвязный список и код быстрее работает. Всё никак не соберусь сделать через двоичное дерево и оно опять же будет реализовано через такие списки, так как удаление для List слишком накладная процедура.
Только я не могу понять в чем разница в скорости доступа для ЦПУ, или перейти по ссылке на ячейку памяти или по индексу, что так же является ссылкой на ячейку памяти. И вы же совсем не обязательно будете обязательно переходить на соседнюю ячейку, а cur = cur->next вовсе не обязан быть в 5 гигабайтах от предыдущего указателя.
забавно, но я в своих решениях часто пользуюсь такими списками и очени быстрые, особенно если вам не нужен доступ по индексу.
Забавно слушать такие рассуждения, когда 1) давно известна сложность различных операций для разного типа коллекций (т.е. не учитыаеется кэш) , и 2) не указана длина коллекции, размер элементов и частота различных операций (уже учитывается и кэш тоже). Это как, напрмер: забавно, но часто я добираюсь до магазина пешком быстрее, чем еду на такси. Конечно, быстрее, если он находится в 5-10 минутах ходьбы. И в чем тут забавность, собственно?
А для примера с OrderBook в общем случае лучше всего map, там все по log(N), но для конкретных размеров стакана (book) и частотности операций могут быть лучше и другие классы, типа deque (коллекция маленьких массивов) или классический двусвязный список. .
Забавно слушать такие рассуждения
а вам не кажется что вам нужно это писать автору, он является первоисточником. Он написал только что такие связные списки это очень медленно. Я же утверждаю что это не так. Если автор не озадачился причинами, то ко мне какие претензии?
или классический двусвязный список
Я делал решение через List, это прилично медленнее чем моя собственная реализация на указателях. Так что ваше или тут не работает. Впрочем моя реализация через указатели работает быстрее и других коллекций доступных в C#.
Я делал решение через List, это прилично медленнее чем моя собственная реализация на указателях
List это ArrayList by default.
об этом и речь, список реализованный через массив работает медленнее той конструкции которая описана в статье, мне кажется очевидно что я именно об этом и написал. самая шлюшка здесь как раз в том, чтобы вставки и удаления происходили быстро без затрагивания остального списка.
А для примера с OrderBook в общем случае лучше всего map, там все по log(N)
я не знаю что такое map, но в C# нет коллекции которая поддерживает порядок элементов, прямую индексацию, быструю вставку и быстрое же удаление. Особенность задачи OrderBook в том, что вы не сможете использовать коллекции на основе хешей, не сможете использовать обычные списки так как они не дадут вам дешевую сортировку и индексацию.
Сейчас у меня решение работает на простом двухсвязном списке как из статьи, оно работает кратно быстрее использования List который даже в отведенное время не успевает отработать. Пока нет настроения, но следующее своё решение я буду делать через сбалансированное двоичное дерево с поддержкой прямой индексации. Но пока не решил, по статистике операций удаления всего 25%, а поддержка прямой индексации обойдется в logN при самом обращении в O(1), нужно будет тестировать, может быть будет проще сделать индексацию по logN из коробки сразу и не создавать еще один массив для индексации.
Только я не могу понять в чем разница в скорости доступа для ЦПУ, или перейти по ссылке на ячейку памяти или по индексу,
Локальность. Указатель может указывать чёрти куда, а массив находится в последовательных адресах и следовательно в той же, или соседней строчке кэша. В свою очередь, чтение из памяти — самая дорогая операция современного процессора.
это совсем не обязательно, например в C# чтобы у вас был последовательный массив нужно использовать fixed, иначе у вас первый элемент будет в 0 байте ОЗУ, а второй в последнем 16 Гб адресе.
В свою очередь, чтение из памяти — самая дорогая операция современного процессора.
Когда вы обрабатываете 10 байт это одно а когда 10 гигабайт это другое.
Нет, массив всегда есть последовательный непрерывный блок памяти.
Оператор fixed просто запрещает GC перемещать блок памяти (на время своего действия).
А как ключевое слово - позволяет объявить инлайн-буфер заданной длины внутри unsafe-структуры.
Когда вы обрабатываете 10 байт это одно а когда 10 гигабайт это другое.
Когда 10 байт лежат рядом в текущей кэш-линии - это одно, а когда их нужно прочитать непосредственно из DRAM - это совсем другое.
что мне всегда нравится в умных программистах из инернетов, это то, что спрашивая у разных "специалистов" получаешь порой диаметрально противоположные ответы и объяснения.
всё что я вам написал про массивы - это не моя придумка, именно так мне объясняли "умные" люди.
Когда 10 байт лежат рядом в текущей кэш-линии - это одно, а когда их нужно прочитать непосредственно из DRAM - это совсем другое.
Есть одна особенность, вам нужно как-то заставить ЦПУ что-то засунуть в кеш. На хайлоад-фан вон целые обсуждения по поводу того как и чем нужно пошевелить на ассемблере, чтобы заиметь шанс работы ЦПУ с данными из кеша. Там вообще уже сложно это называть программированием на C++ (речь про него), так как там по сути инлайны на ассемблере. Так что когда я пишу на C# и пишу такими списками и оно работает быстрее, то мне не так важно что вы там думаете про кеши, 10 байт и ассемблер. Автор никаких специальных уточнений не давал, так что моя претензия в его словам вполне уместна.
Из пальца претензия. У автора рассказаны довольно базовые вещи. А вы не по теме вопрос задали.
У автора рассказаны довольно базовые вещи
На C# я не вижу этому подтверждения.
А вы не по теме вопрос задали.
Я дал комментарий на утверждение автора, оно в принципе не может быть не по теме.
Вы читали тему то, или знакомые слова увидели?
Почему же связанные списке "медленные" могут стать?
dyadyaSerezha вам правильно описал почему ваш вопрос неуместен.
Выделите гига 2 на связанные список
Замерьте время прохода по нему
Размешайте его случайным образом и снова измерьте время прохода
Ключевое слово здесь "не нужен доступ по индексу". На первый взгляд можно бы и согласиться - добавление, вставка и удаление будут быстрее.
Но есть нюансы.
Про кэш-линии уже упомянули.
Но моё любимое - GC.
Мусора такой список создаёт слишком много, чтобы быть быстрым [на более-менее долгом промежутке времени].
Я лично бенчмаркал все стандартные не-массив-бейсед коллекции (включая LinkedList, SortedList и SortedSet), и могу сказать, что для хайлоада они слишком много мусорят. Те, что tree-based - даже при енумерации.
Для себя нашел выход: если действительно не нужен доступ по индексу (и байнари сёрча и т.п.) - лучший вариант это связанный список, но не создающий ноду в куче на каждый элемент, а использующий struct ноды в предварительно выделенных массивах. Да, есть оверхед для учёта и переиспользования свободных/освободившихся слотов в массивах нод, оверхэд на выделение большего массива и копирование данных при добавлении сверх текущей ёмкости, но в целом это гораздо лучший вариант для списков, которые живут дольше одной-двух сборок мусора.
Разве недостаточно просто установить Windows?
Если неважно что писать, а важно чтобы код выполнялся долго, то это классическая задача busy beaver. Там не надо ничего на процессоре замедлять, там есть целая наука писать циклы так чтобы всего времени вселенной не хватило
Знаю, что за очень быстрые алгоритмы платят большие деньги, а сколько вы платите за очень медленные?
байтмашину через функцию Аккермана сделать сможете?
https://in.talent.com/salary?job=Javascript+Developer
выходит от 500-1100$ в месяц.
Говорят, для Гоа самое то)
Хотя утверждается, что быстрый и удобный VS Code написан на JavaScript.
Но чтобы на 3, 4, 5 ГГц тормозил текстовый редактор -- это надо постараться. Бывает, получается: https://github.com/microsoft/TypeScript/issues/44851 до 5 секунд задержка на проверку и аннотацию введенного кода.
Очень много. Новый алгоритм шифрования хотите? Идите писать очень медленный код. Чтобы он на любом проце, включая специализированный асик и проц в которые будут разработаны в ближайшие пару десятилетий, был очень медленным.
Можно еще пошаговую отладку включить, но на Python, думаю, это будет трудновато сделать
Зачем? Страуструп уже сделал всё до вас, по максимуму использовав все слабые места процессора:-)
Как специально написать чрезвычайно медленный код