История изменений
Исправление iVS, (текущая версия) :
Куча концепций, начиная от высоких математический материй до практических реализаций, которые не дотягивают до заявленных теорией высот, зато хорошо делают свою работу. Но тебе же шашечки...
Представь, что есть N элементов из множества 0 ... U. Тогда основное правило в том, что при N, сопоставимом с U, используется массив или хеш-функция; если N значительно меньше U — бинарный поиск. Дело в том, что массив и хеш-функции слишком охотны до памяти, зато дают поиск за O(1); а дерево хорошо экономит память, зато дает O(log N) по времени.
Более возвышенно: нужно отталкиваться от необходимых запросов. Кардинально различаются случаи, когда просто нужно узнать, что элемент находится среди N элементов, или найти конкретный элемент. Вторая задача требует больше ресурсов. Первая задача решается за время O(1) при памяти O(N). Вторая задача при памяти O(N) в общем случае не решается поиском за константное время. Здесь сосредоточена масса работ, которые обозначены как проблема fully indexable dictionary. На сегодня, основной упор делается на хранение больших объемов текста в сжатом виде, при этом сохраняя возможность поиска по нему. Это обширная тематика, кури про Succinct Data Structures.
Исправление iVS, :
Куча концепций, начиная от высоких математический материй до практических реализаций, которые не дотягивают до заявленных теорией высот, зато хорошо делают свою работу. Но тебе же шашечки...
Представь, что есть N элементов из множества 0 ... U. Тогда основное правило в том, что при N, сопоставимом с U, используется массив или хеш-функция; если N значительно меньше U — бинарный поиск. Дело в том, что массив и хеш-функции слишком охотны до памяти, зато дают поиск за O(1); а дерево хорошо экономит память, зато дает O(log N) по времени.
Более возвышенно: нужно отталкиваться от необходимый запросов. Кардинально различаются случаи, когда просто нужно узнать, что элемент находится среди N элементов, или найти конкретный элемент. Вторая задача требует больше ресурсов. Первая задача решается за время O(1) при памяти O(N). Вторая задача при памяти O(N) в общем случае не решается поиском за константное время. Здесь сосредоточена масса работ, которые обозначены как проблема fully indexable dictionary. На сегодня, основной упор делается на хранение больших объемов текста в сжатом виде, при этом сохраняя возможность поиска по нему. Это обширная тематика, кури про Succinct Data Structures.
Исходная версия iVS, :
Куча концепций, начиная от высоких математический материй до практических реализаций, которые не дотягивают до заявленных теорией высот, зато хорошо делают свою работу. Но тебе же шашечки...
Представь, что есть N элементов из множества 0 ... U. Тогда основное правило в том, что при N, сопоставимом с U, используется массив или хеш-функция; есть N значительно меньше U — бинарный поиск. Дело в том, что массив и хеш-функции слишком охотны до памяти, зато дают поиск за O(1); а дерево хорошо экономит память, зато дает O(log N) по времени.
Более возвышенно: нужно отталкиваться от необходимый запросов. Кардинально различаются случаи, когда просто нужно узнать, что элемент находится среди N элементов, или найти конкретный элемент. Вторая задача требует больше ресурсов. Первая задача решается за время O(1) при памяти O(N). Вторая задача при памяти O(N) в общем случае не решается поиском за константное время. Здесь сосредоточена масса работ, которые обозначены как проблема fully indexable dictionary. На сегодня, основной упор делается на хранение больших объемов текста в сжатом виде, при этом сохраняя возможность поиска по нему. Это обширная тематика, кури про Succinct Data Structures.