...или история одного вечера за компьютером :)
Сначала, постановка задачи: есть некая последовательность целых чисел (длина последовательности заранее неизвестна); необходимо определить, есть ли в ней повторяющиеся, и, если есть, определить количество таких повторений (в идеале, для каждого элемента последовательности).
Зачем такое надо? Ну, скажем, может понадобится для статистического анализа некой псевдослучайной последовательности. Или, например, для оценки качества некоторой хеш-функции. Да мало ли...
Для коротких последовательностей (несколько тысяч чисел, до 10 тысяч, наверное) хватило простого лобового решения: несортированный массив значений, поиск последовательным перебором. Потом задачка усложнилась: над массивом отсчетов порядка 100000 элементов программка трудилась почти 30 секунд, при этом это даже не вопрос переаллокации блоков памяти (время практически не зависит от начального размера буфера, я пробовал выделять сразу память под массив из 100000 элементов), как оказалось, операции с памятью довольно быстры. Все тормозил последовательный перебор. Второе лобовое решение --- отсчеты я стал хранить в несбалансированном двоичном дереве --- повысило производительность в десятки раз: время работы программы на том же объеме входных данных составило меньше секунды. Зато и общие затраты памяти увеличились как минимум втрое (+ два указателя на листы дерева). Сейчас думаю над компромиссом. Упорядоченный список не предлагать... :)
Подписаться на:
Комментарии к сообщению (Atom)
Спутник взлетает. Первая ступень отработала.
И, кажется, неплохо: Посмотрим, что будет когда отработает вторая.
-
Арт-группа «Явь» нарисовала на одной из стен петербургских зданий граффити со Стивеном Хокингом : Неизвестно только где.
-
И немного аналитики в тему, хоть и не праздничной: Речь Президента перед Советом Федерации 1 марта 2018 года, которую одновременно называ...
Кидай ссылки.
ОтветитьУдалить