UniLecs138 и небольшие заметки о массивах
@voodoo_woodpeckerЗадача UniLecs №138 является достаточно типичной -- "посмотри в массив/список и выбери что-то нужное" -- и не представляет особой сложности. В прицнипе, есть три подхода к решению (1) просмотреть массив/список, принять решение, и затем выбрать нужное, всё используя функции типа reduce(), map(), filter(); (2) просматривать массив/список, собирая информацию для принятия решения, и параллельно раскидывая элементы в новые массивы/списки потенциальных решений; (3) то же что и во втором случае, но запоминаем не элементы, а их индексы. Все три решения требуют динамических массивов/списков, которые можно менять на лету.
Я ожидало, что второе решение будет наиболее эффективным -- один цикл, но надо больше памяти на два списка , третье наименнее эффективным -- два цикла, второе где-то посредине. На массиве из 10^4 элементов на моей машине получились следующие результаты:
время первой функции 0.47559328216213825
второй -- 0.23076185182670433
третьей -- 71.54164502075638
Честно говоря, я полагал, что разница между первым и вторым решением будет более значительная. В общем, "под капотом" у Питона находятся эффективные, написанные на C библиотеки, так что использование функций типаreduce(), filter(), map() не сильно снижает скорость, но добавляет изяшества и читабельности коду.
В R/Rstudio, язык S заточен под обращение со статистическими данными, так что там очень удобно писать конструкции для работы с векторами, быстро получая, нампример, индексы по условию.
После этого, я задумался, а как обстоят дела в других языках программирования, с которыми я сталкивался, но не программировал.
В Паскале массивы только статические, то есть с жёстко заданными размерами. Это можно обходить заданием максимального размера массива и использованием счётчика реального размера. Во Free Pascal уже есть динамические массивы, а в Delphi есть TList.
На Си довольно позоже на Pascal, просто выделяется память (malloc) и всё, потом можно её realloc (при это указатель может измениться!). На плюсах – std::vector<T> с возможностью push_back(item). Если добавлять по 1 элементу, то с точки зрения скорости шустрее вектор (да он и удобнее, вплоть до for (auto n: vec)), т.к. там идёт выделение не по 1 элементу, а блоками. Не скажу про кол-во элементов в блокове, но допустим 64. Добавляешь первый элемент - память выделилась сразу под 64, дальше 63 просто добавляешь без выделения памяти. Когда добавляется 65-й, выделяется ещё 64 (итого 128).
Благодарю @LostInKadath и @jinxonik за информацию и отличную дискуссию по C/C++/Pascal/Delphi.
В GoLang массивы статичны, но есть динамическая структура "слайс", которая позволяет делать то что нам надо. Классная статья с описанием работы слайсов есть тут "Go Slices: usage and internals"
Решения:
Три варианта на Python: GIST, repl.it
R/Rstudio, язык S: GIST, repl.it