Сообщение Re[6]: свести задачу к мат.модели? от 10.02.2017 14:50
Изменено 10.02.2017 15:34 dinama
Re[6]: свести задачу к мат.модели?
K>И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.
на самом дели три разные ситуации:
1. большинство запросов имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов
в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы
K>Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.
на самом дели три разные ситуации:
1. большинство запросов имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов
в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы
K>Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.
Re[6]: свести задачу к мат.модели?
K>И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.
на самом дели три разные ситуации:
1. большинство запросов не имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов
в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы
K>Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.
на самом дели три разные ситуации:
1. большинство запросов не имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов
в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы
K>Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.