Как искать cidr по ip?

Question

[raiboon]

Есть файлик, ключ-значение, где ключом служит cidr. К нам приходит ip, нужно по этому ip найти значение, желательно за O(1), и держать всё в памяти приложения. Популярные слова и не могу нагуглить модуль или структуру данных для этого.
Есть чего для решения задачи? Либо питоновский, ли на го (давно хотел написать расширение для питона на го)

Answer 1

[throughtheether]

Популярные слова и не могу нагуглить модуль или структуру данных для этого.

На мой взгляд, вам может помочь patricia trie/radix tree. Вот какая-то релевантная имплементация на golang. Вот python-версия.

Answer 2

[jcmvbkbc]

31 мэп IP -> значение, по одному для каждой возможной длины маски. Начинать поиск в том, что соответствует самой длинной маске. O(1) если мэпы отработают за O(1).

Answer 3

[SilentFl]

можно сделать в рамках Go на map'ах (да, jcmvbkbc, они за O(1), у них внутри hash-table), можно сделать на key-value storage (memcache, redis, groupcache, mongo и т.п.)

Comments

[raiboon]

Вы предлагает держать в памяти все ipv4? Уже изобрели бесконечную память?

[SilentFl]

Вы для каждого ipv4 свое значение установили?

Answer 4

[egorsmkv]

Решение с использованием библиотеки iptools:

from iptools import IpRange


def search_cidr(ip, cidrs):
    for cidr in cidrs:
        if ip in IpRange(cidr):
            return cidr

    return False

if __name__ == '__main__':
    cidrs = ['10.0.0.0/30', '10.0.0.5/32']
    your_ip = '10.0.0.2'

    find = search_cidr(your_ip, cidrs)

    if find:
        print('Found:', find)