Оптимальное распределение переменных и динмассивов в памяти

[Joker_vD]

В 2005 году Реймонд Чен писал небольшую программку, которая читала бы txt-файл с китайско-английским словарем и парсила бы его. Писалось на С++, шесть раз переделывалось, пока программа не стала работать "быстро". А некий Рико Мариани (тоже майкрософтовский разработчик) ради хохмы тупо переписал самую первую версию на C# (в лоб, без всяких выкрутасов) и сравнил время работы. Угадайте, где была лучше производительность? Вот реальный график:


Синим показано время работы C++ версии: 5.1 и 5.2 — это пятая версия, багованная и исправленная соответственно. Желтым показано время работы C# программы — перевода самой первой версии С++ программы без всякой оптимизации и с небольшой оптимизацией. Причем чтобы достичь такого увеличения скорости работы С++ программы, Реймонду пришлось: написать собственный файловый ввод-вывод; собственный класс для строк; собственный выделитель памяти; собственный преобразователь кодировок.

Какой отсюда следует главный вывод? Такой, что вся эта оптимизация бессмысленна — ну было полторы секунды, стала одна десятая, ну и что? Тут и пять секунд — приемлемый результат. Зато сколько труда и времени программиста ушло — а время программиста куда дороже времени компьютера.

Так что Sonic86, если интересно — почитайте, конечно, но особо голову не забивайте. Вот если реально будет тормозить, и именно из-за организации работы с памятью... у вас же есть профилировщик, да?.. вот тогда и будете свои структуры данных изобретать.

[Munin]

Joker_vD в сообщении #641768 писал(а):

Такой, что вся эта оптимизация бессмысленна — ну было полторы секунды, стала одна десятая, ну и что?

Ну, в данном случае бессмысленна. А вот если вам удаётся время счёта с месяцев до часов сократить - ещё подумаешь. Впрочем, такие задачи обычно оптимизируются плохо...

[arseniiv]

Sonic86 в сообщении #641673 писал(а):

С другой стороны, мне сказали, что в C++.net есть какие-то двойные списки, в которых 2-й аргумент может быть произвольным типом. TList и THashMap вроде. Если найду, наверное буду их использовать. Неохота мучиться...

Возможно, вы имели в виду generics? Это классы, параметризованные какими-нибудь типами (примерно как шаблоны в C++, но с информацией, доступной во время выполнения, и аккуратной реализацией). Например, типу vector<int> в C++ соответствует List<int> в .NET. Разумеется, параметров-типов может быть много: например, Dictionary<K, V>, реализующий доступ к значениям типа V, индексируя их ключами типа K; он реализован на хеш-таблице и, по идее, аналогичен hashtable из STL, но сколько у этого шаблона параметров — не знаю (если это вообще шаблонный класс). Есть ещё Hashtable, но это не generic, просто класс без параметров, и потому возвращает Object, и к нужному типу надо будет приводить. Есть ещё специализированные классы (параметры сейчас не помню, но должны быть, кроме последнего, те же, что и у Dictionary): HybridDictionary — использует хеш-таблицу при большом числе элементов и список при маленьком, OrderedDictionary — можно индексировать ещё и целыми числами, SortedDictionary — поддерживается упорядоченность записей, StringDictionary — оптимизирован для строк. В STL тоже должно быть разнообразие.

Кстати, имена типов в .NET не начинаются с T (кроме интерфейсов, которые всегда с I и перечислений, которые рекомендуется называть словом во множественном числе).

[Sonic86]

Всем спасибо большое. Значит буду про STL читать. Я про нее пока ничего не знаю. А узнать все прочее было все равно не вредно.

Joker_vD в сообщении #641768 писал(а):

Вот реальный график:

Я его не вижу

Joker_vD в сообщении #641768 писал(а):

Так что Sonic86, если интересно — почитайте, конечно, но особо голову не забивайте. Вот если реально будет тормозить, и именно из-за организации работы с памятью... у вас же есть профилировщик, да?.. вот тогда и будете свои структуры данных изобретать.

Да я просто ознакомится хотел. Просто с самого начала было непонятно, как обращаться к элементам массива, который в памяти разбит на куски. Да и забыл я про С++ - ные типы.
А кто такой профилировщик?
И вообще - я дома балуюсь.

arseniiv в сообщении #641803 писал(а):

Возможно, вы имели в виду generics?

Я не знаю. Мне сказали на слух ключевые слова, по которым искать, я их написал.

Munin в сообщении #641705 писал(а):

Это хорошо бы, но шишки у всех разные, индивидуальные.

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

[Munin]

Sonic86 в сообщении #642375 писал(а):

Я его не вижу

А так?

Sonic86 в сообщении #642375 писал(а):

А кто такой профилировщик?

Profiler, один из важнейших инструментов программиста, занимающегося оптимизацией. Например, http://en.wikipedia.org/wiki/List_of_performance_analysis_tools#C_and_C++

Sonic86 в сообщении #642375 писал(а):

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

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

[Sonic86]

Munin в сообщении #642406 писал(а):

А так?

Вижу, спасибо

Munin в сообщении #642406 писал(а):

Profiler, один из важнейших инструментов программиста, занимающегося оптимизацией. Например, http://en.wikipedia.org/wiki/List_of_pe ... #C_and_C++

Ооо....

Munin в сообщении #642406 писал(а):

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

А, ну тогда да.

[Munin]

(Оффтоп)

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