DP
Думаю что задача разбиения отрезков на непересекающиеся куски сама по себе сложная
Простая, но полнопереборная :)
Size: a a a
2020 March 29
RF
Ага)
RF
В случае когда сами эти отрезки надо часто обновлять получается не очень эффективно
ЕО
Она решается при инсерте за логарифм
АП
Ты понимаешь, что MaxInt64 байта это 16 миллионов террабайт?
что-то ты перемудрил мне кажется
ЕО
В случае когда сами эти отрезки надо часто обновлять получается не очень эффективно
Нужно просто эту структуру данных постоянно держать, вот и всё
RF
что-то ты перемудрил мне кажется
Int64 чисел невозможно в память запихать) нет такого железа
ЕО
что-то ты перемудрил мне кажется
(2^63) байта = 9.22337204 десятичных эксабайта
Говорит нам гугл
Говорит нам гугл
RF
Нужно просто эту структуру данных постоянно держать, вот и всё
Да, тогда этот вариант, наверное, будет работать
ЛА
в случа слайса вообще перебор не надо
Подготовительные действия - полный перебор, дальше поиск конечно простой, но в конечном счёте выходит сложнее, самый просто O(n). Разве нет?
RF
Ну вот и обсудили зачем шаблоны знать
ЕО
Подготовительные действия - полный перебор, дальше поиск конечно простой, но в конечном счёте выходит сложнее, самый просто O(n). Разве нет?
Да он не пихнёт столько данных в память
ЕО
Массив размера MaxUint32 это 4 гигабайта :)
ЛА
Поиск вхождений точки в одномерном отрезке сведётся к бинарному поиску по двум координатам, но это ещё надо будет отрезки так сложить - а это + сложность, + сложность поддержки этого индекса.
Суммарно не вижу, чтобы в худшем случае задача решалась проще, чем простой перебор
Суммарно не вижу, чтобы в худшем случае задача решалась проще, чем простой перебор
АП
(2^63) байта = 9.22337204 десятичных эксабайта
Говорит нам гугл
Говорит нам гугл
ну так то да :(
ЕО
Массив размера MaxUint32 это 4 гигабайта :)
И это вообще любой человек должен помнить, который работал с 32-битными системами
АП
Ну вот и обсудили зачем шаблоны знать
ну тогда не вижу тоже ничего лучше чем перебрать все отрезки
RF
Поиск вхождений точки в одномерном отрезке сведётся к бинарному поиску по двум координатам, но это ещё надо будет отрезки так сложить - а это + сложность, + сложность поддержки этого индекса.
Суммарно не вижу, чтобы в худшем случае задача решалась проще, чем простой перебор
Суммарно не вижу, чтобы в худшем случае задача решалась проще, чем простой перебор
В связи с эти вопрос, а как СУБД так эффективно делают запросы вида curDate<dateTo and curDate>dateFrom (это я образно)
ЛА
В связи с эти вопрос, а как СУБД так эффективно делают запросы вида curDate<dateTo and curDate>dateFrom (это я образно)
Бинарный поиск.
ЕО
В связи с эти вопрос, а как СУБД так эффективно делают запросы вида curDate<dateTo and curDate>dateFrom (это я образно)
Бинарным поиском