Ушат помоев в сторону крестолюбов

Я пытался разобраться в коде QHash из Qt и HashMap из Rust - но так и не осилил. Там тысячи строк кода с кучей неочевидной магии.

Поэтому на бумаге у нас вставка и поиск O(1), что как-бы круто, но в бенчмарках вставка в разы медленнее поиска.

Юноша, я побольше твоего знаю

Отчего же вы тогда так люто говнокодите?

Сложно переплюнуть человека, который употребляет «вы» и «дебил» в одном предложении :D

Кстати, да :-) Женька этим злоупотребляет частенько :-) Лол :-)

Амортизация - это термин из complexity analysts. Грубо говоря затраты в «среднем». Суть в том, что скорость вставки и поиска не зависит от размера хэштаблицы. Будет там 1 или 100500500 элементов.

всяких там иероглифов
новомодных эмодзи
по мере необходимости

2016 год
кодить каким-либо образом привязанный к локали софт
использовать устаревшие строковые типы

Сишка - портянки кода для любой фигни.

Кресты - нечитаемое говно с непредсказуемым поведением.

Тред не читал.

Поэтому на бумаге у нас вставка и поиск O(1), что как-бы круто, но в бенчмарках вставка в разы медленнее поиска.

А что, из того, что оба O(1), как-то следует, что одно не должно быть в разы быстрее другого?

Погугли, что означает это самое O().

алсо для тижолых вычислений еще был фортран :)

Для числодробилок однако либо фортран (если олдскул) либо сейчас те же плюсы однако (ничем не хуже фортрана по производительности если правильно готовить) + CUDA (которая тоже с классами и вот этим всем). Что то я про числодробилки на голых сях и не слыхал почти...

Мне позиция ТС напоминает «Вы все дураки нетрадиционной ориентации, ничего не понимаете и все делаете не так, один я как дэАртаньян в белом пальто стою гордо голову подняв»

Дяденька, а почему у списка операция вставки O(1) а у вектора O(N), а в секундах вставка в список часто медленнее чем в вектор?

Дяденька, а почему у списка операция вставки O(1) а у вектора O(N), а в секундах вставка в список часто медленнее чем в вектор?

Такого быть не может в принципе :-) Есть такая старая песня «Фантазер», ныне модная очень :-)

Мне щас лень тест писать, тем более что ТС скажет - «на этих крестах даже вставка в список медленнее чем в вектор». Пусть сам на сишечке напишет и убедится, речь идет о векторах небольшой длины... ну и аллокатор должен быть правильным;-)

ТС скажет - «на этих крестах даже вставка в список медленнее чем в вектор»

Не думаю, что он так скажет :-) Хотя поинт в том, что на практике зависит от реализации :-) Надо бы проверить, как там с этим случаем в цепепе :-) Вдруг и правда вставка в vector<> быстрее, чем в list<> :-) Лол :-)

В этом то и заключается суть программирования на цепепе :-) Много разговоров, много терминов, много правил, а то, как реально сделано, никто не знает, о чём, собственно OP и пишет :-) Вот ты, например, знаешь, как устроен unique_ptr<>? :-) Посмотри как-нибудь на реализацию :-) Увидишь всякие tuple-сопли и прочее :-) Хотя смарт-поинтер типа unique_ptr, если он уж так нужен, пишется за 3 минуты и без всякого хлама для сверхсупер универсализма вроде default_deleter :-)

Все описано на самом деле.

А насчет не может быть - Вы забываете про то, что выделение памяти на куче очень дорогая операция.

Все описано на самом деле.

Где, в стандарте? :-) Что-то мне подсказывает, что не так много знатоков стандарта C++ в треде :-) Впрочем, это не проблема C++ :-)

А насчет не может быть - Вы забываете про то, что выделение памяти на куче очень дорогая операция.

Я про это помню :-) А помнят ли об этом те, у кого даже здравствуймиры на цепепе приводят к 10 аллокациям? :-)

Если бы помнили, то не говорили бы «не может быть».

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

Язабан всех отметившихся.

o(1) это не значит быстро, а что нет ситуации, когда чем дальше - тем медленней. Если каждая вставка будет занимать 1 день, то это всё еще константа

Поэтому на бумаге у нас вставка и поиск O(1), что как-бы круто, но в бенчмарках вставка в разы медленнее поиска.

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

Ключевые слова тут «алгоритмическую» и «изменения производительности». Эта оценка не позволяет утверждать, что алгоритм а, быстрее алгоритма б.

Например если мы опять говорим о map/unordered_map, то тут надо понимать, что наиболее часто используемый ключ это string. Основными тратами как по мне в обоих структурах являются сравнение строк по operator< для первой и вычисление хэша для второй. По моим оценкам операции сравнения двух строк и вычисления хэша одной строки если и не равны по производительности, то являются операциями одного калибра по производительности, что означает, что unordered_map будет быстрее на картах больше 3 элементов

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

Я к тому, что ТС хвастался, что его вариант O(1), а кресты гавно.

Если бы помнили, то не говорили бы «не может быть».

Как там назвал подобные «если бы», крестоманёвры? :-) Лол :-)

Лично мне нужно что бы я мог в сжатые сроки написать числодробилку с приемлемой производительностью.

Смотря что понимать под «приемлемой производительностью» :-) Вкупе с «в жатые сроки» тут Common Lisp может быть вне конкуренции, особенно, в сравнении с цепепе :-)

вовсе не обязательно выходит посредь площади размахивая обосраными шароварами как флагом. можно просто написать «я умучен от с++» и люди поймут и пожалеют. может быть даже денег дадут.

П - Предсказуемость

Какой то Вы унылый тролль, и клоун из Вас грустный. Всего хорошего.

П - Предсказуемость

U - Undefined Behavior :-)

Какой то Вы унылый тролль, и клоун из Вас грустный. Всего хорошего.

Лол :-) На полном серьёзе говорю, что для прототипирования Common Lisp намного лучше, чем цепепе :-) Числодробильня там не хуже, чем в Java, во всяком случае :-) Арифметика произвольной точности из коробки, не то, что в цепепе :-) А результат достигается намного быстрее :-) Но ты же будешь продолжать кодить на цепепе, потому что изучать Лисп в лом :-) Так же? :-)

Я бы Вас послушал с интересом, если Вы написали на CL хоть одну серьезную числодробилку. Ну или привели бы пример такой числодробилки. А так - Вы унылый тролль и грустный клоун.

Я бы Вас послушал с интересом, если Вы написали на CL хоть одну серьезную числодробилку. Ну или привели бы пример такой числодробилки.

Что такое «серьёзная числодробилка»? :-) Вот я могу на Лиспе написать банальнейший однострочник суммирования первых 10 миллиардов натуральных чисел :-) Если это «серьёзная числодробилка», тот вот (loop for i from 0 to 10000000000 sum i) :-) Результат 50000000005000000000 :-) Написал этот текст программы за 5 секунд, а на моём, весьма скромном лаптопе, расчёт занял 270 секунд :-) Сравним с цепепе? :-)

А так - Вы унылый тролль и грустный клоун.

Ну уж точно не академик РАН :-)

да ты знаешь все синтетические тесты, для которых специально затачивали лиспворкс? :)

Сравним с цепепе? :-)

Зачем с цепепе? Для прототипирования есть другие языки. Зачем возиться с нечитабельным Лишпом, когда есть Питон, Руби и всякое такое?

(loop for i from 0 to 10000000000 sum i)

sum(range(10000000001))

Для прототипирования есть другие языки. Зачем возиться с нечитабельным Лишпом, когда есть Питон, Руби и всякое такое?

Хахаха :-) Не мог бы ты на читаемом Питоне или Руби запустить этот твой sum(range(10000000001)) и засечь время расчёта? :-) Лол :-)

Не мог бы ты на читаемом Питоне или Руби запустить этот твой sum(range(10000000001)) и засечь время расчёта? :-)

~6 минут. И?

Поэтому на бумаге у нас вставка и поиск O(1), что как-бы круто, но в бенчмарках вставка в разы медленнее поиска.

Ты просто не понимаешь значение O(1)... Кому я писал про «не зависит от размеров таблицы»?!

~6 минут. И?

И сливает Питон на порядок, как минимум :-) Суммирование одного миллиарда 1-х нат. чисел на Питоне на моей машине занимает 27 секунд, против 2.2 секунд на Лиспе :-) Такие дела :-)

Вкупе с «в жатые сроки» тут Common Lisp может быть вне конкуренции, особенно, в сравнении с цепепе :-)

Настоящий программист(tm) может написать числодробилку на CL и компилятор деревьев на фортране :)))

(loop for i from 0 to 10000000000 sum i)

Да, GMP штука хорошая и быстрая.

вот видишь, ты пишешь несерьёзные числодробилки.

числодробилки — SERIOUS BUSINESS.

Суммирование одного миллиарда 1-х нат. чисел на Питоне на моей машине занимает 27 секунд

Каким интерпретатором суммировал?

Да, GMP штука хорошая и быстрая.

Может быть :-) Но данный расчёт выполнил SBCL, а не GMP :-)

Каким интерпретатором суммировал?

Python 3.5.2 :-)

Python 3.5.2 :-)

У меня на Python3 миллиард тоже 27 секунд. А на pypy - 1.3 секунды. Так-то.

У меня на Python3 миллиард тоже 27 секунд. А на pypy - 1.3 секунды. Так-то.

А 10 миллиардов за 6 минут, это тоже pypy? :-)

Посчитал вручную без GMP.
Вот исходник: https://gist.github.com/olegchir/91acba30cbdc0fb971b03d59a34eeff4

На 10 миллиардах: 228 секунд (где-то 30% проца не используются, потому что забиты разным софтом, который нельзя выгрузить, но зато и процессор десктопный).

На 1 миллиарде: 24 секунды

Т.е. цифры в точности такие же, как у анойнимуса. Короче, природу не обманешь - сколько в проце мощи есть, столько он и выдает.

Озадачило, что лисповский джит (лисп - язык на котором никто не пишет) умудряется увидеть паттерн и собрать в примерно такой же код как у джавы, а питоновский - нет. Или у питона до сих пор нет джита?

А на pypy - 1.3 секунды

здается мне ты врешь как дышишь
закежь что там в ассемблере творится, во что собралось

На 1 миллиарде: 24 секунды

У меня 1 миллиард суммируется за 2.2 секунды :-) А если добавить тип, то вообще за 0,7 секунды:

CL-USER> (time (loop for i fixnum from 0 to 1000000000 sum i fixnum))
(LOOP FOR I FIXNUM FROM 0 TO 1000000000 SUM I FIXNUM)

CL-USER> (time (loop for i fixnum from 0 to 1000000000 sum i fixnum)) (LOOP FOR I FIXNUM FROM 0 TO 1000000000 SUM I FIXNUM) took 781,171 microseconds (0.781171 seconds) to run.

А 10 миллиардов за 6 минут, это тоже pypy? :-)

Это cpython2.

Или у питона до сих пор нет джита?

У основного интерпретатора - нет. На то pypy и сделали.

здается мне ты врешь как дышишь

time python3 -c 'print(sum(range(1000000001)))'
500000000500000000

real	0m26,405s
user	0m26,176s
sys	0m0,000s

time pypy -c 'print sum(xrange(1000000001))'
500000000500000000

real	0m1,354s
user	0m1,336s
sys	0m0,004s

Ассемблер ещё нужен? А то я для jit не шибко умею его смотреть.

А вот это кто писал, и почему такая разница?

Вот пруфы для миллиарда в одном месте ещё раз:

CL-USER> (time (loop for i from 0 to 1000000000 sum i))
(LOOP FOR I FROM 0 TO 1000000000 SUM I)
took 2,277,193 microseconds (2.277193 seconds) to run.

CL-USER> (time (loop for i fixnum from 0 to 1000000000 sum i fixnum))
(LOOP FOR I FIXNUM FROM 0 TO 1000000000 SUM I FIXNUM)
took 781,171 microseconds (0.781171 seconds) to run.