Comments 32
интерпретаторы это тоже жульничество по вашим же критериям. это vm, а не конкретное устройство и все вычислительные ресурсы это ресурсы обслуживания вирт машины.
забавно, но я в своих решениях часто пользуюсь такими списками и очени быстрые, особенно если вам не нужен доступ по индексу.
Забавно слушать такие рассуждения, когда 1) давно известна сложность различных операций для разного типа коллекций (т.е. не учитыаеется кэш) , и 2) не указана длина коллекции, размер элементов и частота различных операций (уже учитывается и кэш тоже). Это как, напрмер: забавно, но часто я добираюсь до магазина пешком быстрее, чем еду на такси. Конечно, быстрее, если он находится в 5-10 минутах ходьбы. И в чем тут забавность, собственно?
А для примера с OrderBook в общем случае лучше всего map, там все по log(N), но для конкретных размеров стакана (book) и частотности операций могут быть лучше и другие классы, типа deque (коллекция маленьких массивов) или классический двусвязный список. .
Только я не могу понять в чем разница в скорости доступа для ЦПУ, или перейти по ссылке на ячейку памяти или по индексу,
Локальность. Указатель может указывать чёрти куда, а массив находится в последовательных адресах и следовательно в той же, или соседней строчке кэша. В свою очередь, чтение из памяти — самая дорогая операция современного процессора.
Нет, массив всегда есть последовательный непрерывный блок памяти.
Оператор fixed просто запрещает GC перемещать блок памяти (на время своего действия).
А как ключевое слово - позволяет объявить инлайн-буфер заданной длины внутри unsafe-структуры.
Когда вы обрабатываете 10 байт это одно а когда 10 гигабайт это другое.
Когда 10 байт лежат рядом в текущей кэш-линии - это одно, а когда их нужно прочитать непосредственно из DRAM - это совсем другое.
Из пальца претензия. У автора рассказаны довольно базовые вещи. А вы не по теме вопрос задали.
Вы читали тему то, или знакомые слова увидели?
Почему же связанные списке "медленные" могут стать?
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, думаю, это будет трудновато сделать
Зачем? Страуструп уже сделал всё до вас, по максимуму использовав все слабые места процессора:-)
Как специально написать чрезвычайно медленный код