Сообщение Re[5]: свести задачу к мат.модели? от 10.02.2017 14:28
Изменено 10.02.2017 14:46 ksandro
Re[5]: свести задачу к мат.модели?
Здравствуйте, dinama, Вы писали:
D>коллекция к которой делается запрос — неизменяема.
D>а запросы могут быть разные.
D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
D>300000 тысяч ключей.
Мы оптимизируем память или время работы?
Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.
И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.
D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)
Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
D>коллекция к которой делается запрос — неизменяема.
D>а запросы могут быть разные.
D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
D>300000 тысяч ключей.
Мы оптимизируем память или время работы?
Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.
И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.
D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)
Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
Re[5]: свести задачу к мат.модели?
Здравствуйте, dinama, Вы писали:
D>коллекция к которой делается запрос — неизменяема.
D>а запросы могут быть разные.
D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
D>300000 тысяч ключей.
Мы оптимизируем память или время работы?
Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.
Хэш таблица будет хранить не все 300000 ключей а их хеши, которых будет меньше. Но если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат. В изначальном примере было только 2 атрибута.
D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)
Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
D>коллекция к которой делается запрос — неизменяема.
D>а запросы могут быть разные.
D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
D>300000 тысяч ключей.
Мы оптимизируем память или время работы?
Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.
Хэш таблица будет хранить не все 300000 ключей а их хеши, которых будет меньше. Но если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат. В изначальном примере было только 2 атрибута.
D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)
Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?