Предподсчет и поиск за одну секунду

Здравствуйте!
Поставлена такая задача: имеется массив из 100,000 пар "строка - число". Все строки уникальные, числа могут повторяться. Даётся 1 секунда на создание вспомогательных структур и предподсчет будущих результатов. После этого следует 100,000 запросов, в каждом из которых выполняется поиск 10 таких пар, что: строка начинается с указного префикса, а число как можно больше.
Выполнение всех этих запросов должно уложиться ещё в 1 секунду!
И ещё одно неприятное ограничение: используемая память ограничена 64 мб.

Подскажите, какие структуры можно использовать для решения?
Префиксное дерево (первое, что пришло в голову) уже безо всяких предподсчетов не укладывается в 64 мб. AVL-дерево по памяти проходит, но на выполнение одного запроса уходит (в среднем) 5 мс - слишком медленно.
Подскажите ещё варианты?

0

Какого размера числа?
Какой длины строки?

Добавлено через 1 час 3 минуты
Какие символы могут встречаться в строках?

1

ну, без дерева точно никуда тут
по сути, имитируем поиск в БД с индексами

если строка 25 + число 4 то всего 2 мб набирается данных
что бы в 64 мб не уложиться с индексами ?

1

Числа - long, по 8 байт каждое. Строки - не более 32 символов в unicode, только буквы и цифры. Итого 72 байта на одну пару, ~7 мб на все данные.

Опыты показали, что при таких условиях количество узлов в префиксном дереве приближается к 3 миллионам, то есть построить его целиком не выйдет - не хватит памяти.

Сейчас рассматриваю такой вариант: префиксное дерево для первых 8 символов (займет около 50 мб), дальше обычное дерево или даже просто список. Но быстро работать это будет только из расчета, что лишь несколько строк начинаются с 8 одинаковых символов.
Да и, честно говоря, пока слабо представляю, как это всё написать.

Ещё не указал одну деталь: реализовываться будет на Java.

0

можно закинуть хеши всех префиксов в std:map<long long, int> - МАП из хеша префикса в макс число. ну и потом когда пришел запрос мы просто считаем хеш строки-запроса и берем значение из МАПЫ.

0

префиксы для поиска фиксированной длины?

0

krapotkin, не понял вопроса. вот есть строка S и соответствующее ей значение VAL. мы посчитаем хеши всех префкисов строки и все эти хеши закинем в МАП так: MAP[hash[i]] = max(MAP[hash[i], VAL); теперь когда пришел запрос строка мы считаем ее хеш. пусть он равен needHASH и тогда ответ на запрос равен MAP[needHASH].

Добавлено через 2 минуты
Dozer74, кстати откуда задача. чет она больно олимпиадная да еще и ограничения откуда то взялись. может соревнование какое идет?

0

в задании сказано
10 таких пар, что: строка начинается с указного префикса, а число как можно больше
если префиксы фиксированной длины, то вполне можно эффективный индекс построить
я просто не знаю, как хэши реализованы в яве

0

В качестве ключей я создаю случайным образом 100 тыс. строк по таким параметрам:
Я строю дерево. Узлов в нём меньше, чем 150 тыс.
Время на построение меньше 0.5сек.

Случайным образом строю 100 тыс запросов.
Выполняю все запросы.
Общее время меньше 0.05сек.

Добавлено через 4 минуты
Описание дерева:

Добавлено через 9 минут
Мне лень было самому двоичный поиск в отсортированном массиве писать , поэтому я использую SortedList<char, int>:
SortedList<TKey, TValue> is implemented as an array of key/value pairs, sorted by the key.
The SortedList<TKey, TValue> generic class is an array of key/value pairs with O(log n) retrieval.

Так выглядит узел дерева:
Нужно его заменить на структуру Node с полями: char, long, *Node, где *Node - ссылка на отсортированный массив.

Добавлено через 8 минут
Алгоритм построения дерева:
1. Сортируем данные по ключу (строке).
2. Для каждой строки данных:
Пока префикс ключа совпадает с префиксом предыдущего: идём по дереву, обновляя, если нужно число.
Добавляем узел с текущим символом ключа.
Пока префикс не станет отличаться от префикса следующего: добавляем узел с текущим символом.

Добавлено через 5 часов 42 минуты
Запускал я только дебаг версию (без оптимизации). С оптимизацией немного быстрее получается.

Я переписал с использования SortedList на обычный List (обычный массив с логикой для автоматического увеличения размера). Так как массивы у меня маленькие, то линейный поиск не сильно медленней получается.

А вот с памятью сложнее. Для оптимизации по памяти нужно свой менеджер памяти писать, а мне лень (массивы по ходу работы нужно переаллоциловать - значит за "дырками" следить и т.д.). Потом каждый экземпляр класса - это дополнительный расход памяти. Класс нужно на структуру заменять, а в C# нельзя структуру из функции по ссылке вернуть... значит код переписывать. Сейчас по памяти я укладываюсь с большим запасом... но это на случайных данных. Неизвестно, что будет, если специально конструировать данные, которые потребуют максимума памяти.

Сейчас время примерно такое:
Generate tree: max = 100000, time = 00.0771723
Memory used: 43,56 Mb
Find: max = 100000, time = 00.0589016

Добавлено через 3 минуты
Расход памяти - это то, что процесс под себя забирает. Я из под LinqPad запускал... там даже при n = 10 сразу 32 Mb...

Добавлено через 4 минуты
С линейным поиском в два раза медленнее ищется, но запас есть.

0

Не понял что здесь дает дерево если оно строится по одному ключу (строка). Просто отсортированный массив и линейный поиск в диапазоне lower_bound/upper_bound даст ту же скорость. Если все строки начинаются c заданного префикса - увы, дело сведется к линейному перебору.

Заменим строку на "тоже число", получаем задачу: найти точку (x, y) с максимальным y и x в заданном диапазоне значений. Здесь хорошо подходит напр BSP, AABB - т.е. задача сводится к хорошо известной. Просто это замаскировано "строкой" (и ловушка сработала )

0

Сообщение от Igor3D Не понял что здесь дает дерево если оно строится по одному ключу (строка).

Я, наверное, непонятно объяснил. Проще показать на примере.

Вот исходные данные и дерево, которое я строю:
(на синие числа не обращайте внимания - их линкпад добавляет при выводе.

Миниатюры

   

0

Сообщение от Shamil1 Я, наверное, непонятно объяснил. Проще показать на примере.

Все равно не понял в чем смысл Ну вот допустим все строки начинаются с "а" который и есть префикс. Будут ли перебраны все эл-ты Вашего дерева или все-таки оно что-то отсечет?

0

Сообщение от Igor3D у вот допустим все строки начинаются с "а" который и есть префикс.

В списке, состоящем из единственного элемента, найдёт узел Char == 'a'. И тут же вернёт ответ - значение Number данного узла.

Добавлено через 4 минуты
На картинке видны ответы (максимальные числа) для всех префиксов:

1

Сообщение от Shamil1 В списке, состоящем из единственного элемента, найдёт узел Char == 'a'. И тут же вернёт ответ - значение Number данного узла.

Теперь понял, спасибо. Да, быстрее поиск пожалуй не сделать

0