|
Тяпничная география
|
|||
---|---|---|---|
#18+
Это та-же биткарта. Но я принципиально не хочу решать задачу в SQL так-же как я и решал бы ее на сях. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2015, 14:21 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Получил несолько ложных срабатываний. Разобрался. Забыл что отрезки сами с собой пересекаются. Убрал само-соединение. Пока пишу... в процессе. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2015, 14:35 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Задача не заточена под SQL, подобные проблемы обычно биткартой решают. Например в задачах с диапазонами дат используют вспомогательную таблицу-календарь со всеми датами. Пробуй: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
Возможно 4 вида перекрытия отрезков: справа, слева, сверху и снизу. При сравнении всем со всеми можно упростить до проверки только слева и сверху, т.к.: A слева перекрывает B == B справа перекрывает A A сверху перекрывает B == B снизу перекрывает A заодно дубли уберутся. Будут ли использоваться индексы и какие не знаю. Сделай два: (n_startip, n_endip) и (n_endip, n_startip), СУБД сама разберется нужны они или не очень. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2015, 14:44 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Чуть упростил: Код: plaintext 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2015, 15:00 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Я надеялся двумя предикатами обойтись. Тоже сидел грыз гранит предикатов max/min и сравнений. Пока плюнул. Работа подвалила. Вечером вернусь к географии. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2015, 15:08 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Этот код по-моему должен работать, но работает некорректно Код: plaintext 1. 2.
Может быть я неправильно его использую в своём контексте, попробуйте у себя ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 02:27 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima TПервая корявая получилась. Хотел допилить кавычки и в свою библиотеку прибрать, пригодится, потом подумал обычно надо еще знать сколько всего колонок прежде чем парсить. Получилось проще новую написать :) Твой файлик проходит без ошибок. Спс. Закоммитил. С небольшими изменениями. Будет как базовый алгоритм. https://sourceforge.net/p/countryipdiagram/code/HEAD/tree/trunk/src/ipv4filter.c ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 10:34 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima TЧуть упростил: Код: plaintext 1. 2. 3. 4.
Попробуй нагенерить 5 млн случайных строк. Потому как я на Оракле не могу дождаться завершения работы этого курсора. Здесь не проблема его написать. А проблема написать оптимально. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 13:04 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
SashaMercuryЭтот код по-моему должен работать, но работает некорректно Код: plaintext 1. 2.
Может быть я неправильно его использую в своём контексте, попробуйте у себя Посмотрю чуть позже. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 13:27 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
maytonПопробуй нагенерить 5 млн случайных строк. ИМХУ нездоровый тест. Индексы не только сортировка, но и распределение. А также результат: если у тебя пересечений не ожидается, то будет мало, а в рандоме может 100 тыс. пересечься друг с другом и будет 100`000 * 100`000 / 2 = 5`000`000`000 записей ответа. maytonПотому как я на Оракле не могу дождаться завершения работы этого курсора. Ты индексы создал? Я выше писал: Сделай два: (n_startip, n_endip) и (n_endip, n_startip), СУБД сама разберется нужны они или не очень. Затем план выполнения запроса смотри, там будет сразу видно использует индексы или нет. Как в оракле смотреть не знаю. Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 13:56 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima TТы индексы создал? Чел я же не просто так скрипты привёл. 17382368 Они реальны и работают. По поводу плана исполнения - отпишу чуть позже. Я не привык писать с бухты-барахты и обычно проверяю. Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как. Ты не поверишь но я над этим думаю. Скорее всего эта БД весьма специфична по сути. Например движок MaxMind и Java-имплементация базы (втроенная) занимала размер многократ меньше чем CSV-файл. Для таких данных обычно юзают префиксное дерево или дерево остатков. Вполне возможно что оно там и заюзано. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 14:48 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima TКстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как. Придумал: хранить в двоичном текстовом виде выравненном до 32 c обрезанными конечными ноликами. Формула обрезки: (n_endip - n_startip), проверяем на вид 0000011111 (т.е. сначала нули, затем единицы) или тоже самое на соответствие (2^n - 1), n - сколько младших бит обрезать от n_startip. Пример на 4 битах НачалоКонецХраним07047014501081110121511 дальше сортируем по храним как строки и сравниваем предыдущую с последующей в количестве символов первой - совпало - вторая входит в первую, т.е. "0" == "01" (выкидываем "01"), затем "0" == "010" (выкидываем "010"), затем "0" != "10", затем "10" != "11" Одна сортировка, один проход, без биткарты, но опять не заточено под SQL ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 15:03 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Сделай проверку на валидность: Код: plaintext 1.
Дальше подзабыл, если больше 65535 будет то это ряд (2^n - 1) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 15:12 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima TСделай проверку на валидность: можешь не делать, 10% твоего файла не проходит maytonDima TТы индексы создал? Чел я же не просто так скрипты привёл. 17382368 Они реальны и работают. По поводу плана исполнения - отпишу чуть позже. Я не привык писать с бухты-барахты и обычно проверяю. Залил твой файлик в MSSQL. Мой запрос без индексов 10 сек, с индексами 16 сек ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 16:20 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Придумал! Выстроить цепочку: n_prev_startip = 0 n_prev_endip = 0 1. Взять запись с минимальным n_startip больше n_prev_startip 2. Если n_startip < n_prev_endip значит наложение 3. n_prev_endip = n_endip, n_prev_startip = n_startip 4. если не все пройдены перейти к пункту 1. Имеем 5 млн. поисков макс. по 24 шага каждый, т.е. ~100 млн операций. код на фоксе Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31.
Твои 10 тыс проверились за 20 мс :) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 17:16 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima T, минутку. Я всё-тки проверю свои 5 млн. Подожди. P.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся. Интересовало портирование этого алгоритма в другие DBMS. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 19:15 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Капец. План вообще никчорту! Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67.
Какого осьминога ему тут нужен PRIMARY key??? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 19:34 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
alter index ... invisible помог. Хорошая шняга в одинадцатом жигуле Оракле... Мдя. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 19:40 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 19:42 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Два мильйона. Это примерно половина всей базы . Код: plsql 1. 2. 3.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 19:58 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
maytonP.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся. Интересовало портирование этого алгоритма в другие DBMS. rushmore В данном случае можно ассоциативным массивом обойтись. arr[start_ip] = end_ip. Например <map> в С++ В SQL он не впишется, т.к. противоречит концепции реляционных БД. Через одно место можно попробовать впихнуть, но оно и будет работать соответственно. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 20:01 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
maytonДва мильйона. Это примерно половина всей базы . Код: plsql 1. 2. 3.
Забей на проверку масок, идея не взлетела, я же проверил на твоем файлике, выше писал. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 20:03 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Я замудрено придумал, проще так: сортируем по n_startip идем последовательно если текущий n_startip < предыдущий n_endip значит перекрытие Одна сортировка, один проход. Лучше не будет. это с небольшими извратами можно даже в оракле/мсскул селектом выбрать. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 20:12 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Dima T, +1. Это будет констрейнтом в работе самого приложения. Во врема парсинга будет просто происходить проверка двух соседник строк на перекрытие диапазонов. Так и сделаем. А самую первую (изначальную) сортировку по beginIp можно сделать в оффлайне и пересохранить исходный файл. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2015, 20:20 |
|
Тяпничная география
|
|||
---|---|---|---|
#18+
Хм... самопальный IP2num не взлетает. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26.
Чортовы сишные сдвиги. Наверное где-то разрядная сетка рубится. Код: php 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2015, 00:43 |
|
|
start [/forum/topic.php?fid=57&msg=38905938&tid=2017270]: |
0ms |
get settings: |
8ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
141ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
52ms |
get tp. blocked users: |
1ms |
others: | 12ms |
total: | 247ms |
0 / 0 |