ФорумПрограммированиеPHP для идиотов → Пересечение множеств в бд - профи обосрались?!

Пересечение множеств в бд - профи обосрались?!

  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 8:07

    короче задачка - есть пулы ип адресов, они пересекаются, их много ~ 500 тыс строк. отсортированы в порядке уменьшения размера пула. как это дело "пересечь", то есть

    например для ипа

    212.45.5.198

    select id,ip_from,ip_to,data1,data2,data3,ip_to-ip_from from ranges where 3559720390 BETWEEN ip_from and ip_to

    108060 3559718912 3559727103 176 0 0 8191
    242774 3559718912 3559727103 176 728 1001 8191
    242898 3559720384 3559720391 176 728 1001 7



    ну чо фабьен? обоссался?)
    Спустя 220 сек.
    это одноразовая операция, поэтому на скорость в принципе похуй, если будет выполняться пару минут или немногим больше)
    Сапожник без сапог
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 8:31, спустя 24 минуты 14 секунд

    Пересечения диапазонов значений, а не множеств?

    Диапазоны НЕ пересекаются если
    a.ip_to < b.ip_from OR a.ip_from > b.ip_to
    накладываем отрицание и получаем искомое:
    NOT (a.ip_to < b.ip_from OR a.ip_from > b.ip_to)
    или то же самое
    a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from

    Для параметров $from, $to

    SELECT a.id, a.ip_from, a.ip_to
    FROM ranges AS a
    WHERE a.ip_from <= $to AND a.ip_to >= $from


    Самоперечечение

    SELECT a.id AS aid, b.id AS bid, min(a.ip_from, b.ip_from) AS ip_from, max(a.ip_to, b.ip_to) AS ip_to
    FROM ranges AS a, ranges AS b
    WHERE a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from

    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 8:33, спустя 1 минуту 31 секунду

    artoodetoo, я чуток не это видимо имел ввиду судя по запросу, мне надо разбить всю базу на БОЛЬШЕЕ количество отрезков у которых будут концы - начала меньших подмножеств :)

    то бишь если по руски было

    1 .. 15
    4 .. 5

    станет

    1 .. 4
    4 .. 5
    5 .. 15

    :)
    Сапожник без сапог
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 8:53, спустя 20 минут 18 секунд

    ну это почти то же самое.
    1) находим пересекающиеся отрезки
    2) выводим четыре точки min, middle1, middle2, max
    точки min и middle1, а также middle2 и max теоретически могут совпадать — дальше уже скрипт должен решать сколько здесь диапазонов: возможно от 1 до 3

    я немного наврал по поводу использования min() и max() — их нельзя использовать со значениями, только как аггрегатные, вместо этого есть
    LEAST() - аналог min() в PHP
    GREATEST() — аналог max() в PHP

    SELECT a.id AS  aid, b.id AS  bid,
     least(a.ip_from, b.ip_from) AS ip_min,
     greatest(a.ip_from, b.ip_from) AS ip_middle1,
     least(a.ip_to, b.ip_to) AS ip_middle2,
     greatest(a.ip_to, b.ip_to) AS ip_max
    FROM ranges AS a, ranges AS b
    WHERE a.ip_from <= b.ip_to AND a.ip_to >= b.ip_from
    Спустя 112 сек.
    если надо выбрать только те пары, диапазоны, которые бьются на три — делаем условие строже
    [tt]a.ip_from < b.ip_to AND a.ip_to > b.ip_from[/tt]
    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 8:59, спустя 6 минут 18 секунд

    возможно красавец)) но я уже на c# пишу утилку для этой задачки, ибо на мускуль не надеюсь))
    Сапожник без сапог
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 9:01, спустя 1 минуту 29 секунд

    не "возможно", а точно
    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 9:15, спустя 14 минут 5 секунд

    artoodetoo, возможно - потому что диапазонов вложенных бывает больше 2ух)) штук 10 может быть легко
    Спустя 18 сек.
    подождал минуту выполнения твоего запроса и понял что наверное безнадежно ))))))))))))))))))))))))
    Сапожник без сапог
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 10:10, спустя 55 минут 27 секунд

    добавил еще a.id < b.id в наивной попытке сократить число сравниваемых пар

    SELECT a.id AS aid, b.id AS bid,
    least(a.ip_from, b.ip_from) AS ip_min,
    greatest(a.ip_from, b.ip_from) AS ip_middle1,
    least(a.ip_to, b.ip_to) AS ip_middle2,
    greatest(a.ip_to, b.ip_to) AS ip_max
    FROM ranges AS a, ranges AS b
    WHERE
    (a.id < b.id) AND
    (a.ip_from < b.ip_to AND a.ip_to > b.ip_from)
    ORDER BY a.id


    однако!!! прикинь, если записей 1000, то необходимо сравнить где-то 1000*1000/2 диапазонов. у меня на локалхосте порядка 20сек занимает с выводом
    а на 500k записях будет намного дольше :) я не вижу способа как кардинально ускорить.
    1. ranges.zip (28)
    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 10:00, спустя 23 часа 49 минут 32 секунды

    а на 500k записях будет намного дольше :) я не вижу способа как кардинально ускорить.

    на c# я написал мержер, который делает эту работу за 4 секунды с небольшим)
    Сапожник без сапог
  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 10:06, спустя 5 минут 55 секунд

    все держит в оперативке?
    ιιlllιlllι унц-унц
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 2 сентября 2010 г. 10:15, спустя 9 минут 12 секунд


    все держит в оперативке?
    нет :)

    ну это тоже конечно, просто не все пересчитывает)
    Сапожник без сапог
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 3 сентября 2010 г. 1:29, спустя 15 часов 13 минут 56 секунд

    вы все еще используете бд?)

    я написал поиск по всей этой хуйне, который в 100 раз ебет в зад мускуль :D

    Спустя 33 сек.
    решил не пересекать множества вообще, так и ищет несколько диапазонов
    Сапожник без сапог
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 3 сентября 2010 г. 1:31, спустя 2 минуты 7 секунд


    вы все еще используете бд?)

    [подъеб]а как ты все это сделал без бд?[/подъеб]
    Спустя 17 сек.
    а почему тэг [подъеб] не работает?
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 3 сентября 2010 г. 1:32, спустя 42 секунды

    а почему тэг [подъеб] не работает?

    можем выписать тебе свн :)
    Сапожник без сапог

Пожалуйста, авторизуйтесь, чтобы написать комментарий!