Какой алгоритм поиска выбрать

@Колков · Регистрация: 16.04.2015

Студворк — интернет-сервис помощи студентам

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

C++
1
2
3
4
5
6
7
struct MyData
{
    int index;
    int age;
    int sex;
    int date;
};

Необходимо найти все элементы по некоторымм параметрам, параметры поиска могут быть от 1 до 4 и разных комбинаций полей.
Каким лучше всего алгоритмом поиска воспользоваться, я кроме линейного поиска ничего не смог придумать, но работает медленно и есть возможность, что в недалёком будущем этот массив может стать в 10 раз больше и поиск может надолго подвиснуть. Заранее спасибо за помощь!

@Renji · 23.03.2017, 18:02

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

@igorrr37 · 24.03.2017, 09:18

https://habrahabr.ru/post/160009/

MrGluck · 24.03.2017, 12:13

Сразу встаёт вопрос а что делает поле index в этой структуре? Если мы будет хранить структурные переменные в массиве, то итак будем знать index элемента.
И почему поле sex имеет тип int? Там много вариантов?

@GbaLog- · 24.03.2017, 12:15

Не по теме:

Сообщение от MrGluck

Там много вариантов?

Как минимум 3, столько в bool не влезет. :rofl:

MrGluck · 24.03.2017, 12:27

Не по теме:

Кроме шуток, недавно видел код, где переменная типа BOOL (WinAPI-ный) принимала значения 0, 1 и 2! И позже в другом месте это учитывалось.

У меня в голову лезет идея с составным ключом, состоящем из комбинаций значений age (3 цифры), date (ну пусть будет 4 цифры, хотя не знаю точно что там за даты собираются хранить), sex (хватит и 1). 8-значное число будет являться индексом (или ключом если хранить в хеше) к однозначному набору элементов с заданными хар-ками.
Можно, конечно, это всё на биты попробовать перевести, но и так нормально.

Новые блоги и статьи Все статьи Все блоги /
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	23.03.2017, 18:02
	1) Строить индекс по составному ключу, для всех возможных комбинаций полей. Ну да, число индексов растет по факториалу, но для четырех полей цифры вполне приемлемые. 2) Строить индекс для каждого поля отдельно. Поиск по нескольким полям одновременно реализовать в форме "ищем по полю А, ищем по полю Б, потом отбираем записи найденные в первом и втором поиске разом". Первый вариант будет жрать память как конфеты, для второго можно подобрать входной массив на котором алгоритм все равно скатится до линейной сложности. 0

@igorrr37 2872 / 2019 / 991 Регистрация: 21.12.2010 Сообщений: 3,754 Записей в блоге: 9
	24.03.2017, 09:18
	https://habrahabr.ru/post/160009/ 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	24.03.2017, 12:13
	Сразу встаёт вопрос а что делает поле index в этой структуре? Если мы будет хранить структурные переменные в массиве, то итак будем знать index элемента. И почему поле sex имеет тип int? Там много вариантов? 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	24.03.2017, 12:27
	Не по теме: Кроме шуток, недавно видел код, где переменная типа BOOL (WinAPI-ный) принимала значения 0, 1 и 2! И позже в другом месте это учитывалось. У меня в голову лезет идея с составным ключом, состоящем из комбинаций значений age (3 цифры), date (ну пусть будет 4 цифры, хотя не знаю точно что там за даты собираются хранить), sex (хватит и 1). 8-значное число будет являться индексом (или ключом если хранить в хеше) к однозначному набору элементов с заданными хар-ками. Можно, конечно, это всё на биты попробовать перевести, но и так нормально. 0