Как быстро сравнить два url?

Question

[tutunak]

Доброго времени суток!

Стоит задача сравнивать поподающие в систему новыу url файлов на уникальность. количество уникальных url в файле несколько сотен тысяч. Как я понимаю сравнивать полностью строки не очень эффективно. Появилась мысль, что можно сравнивать хеши этих строк. Коллизиями можно пренебречь. Какую базу данных выбрать для хранения hash? Я не нашел в sqlite возможности хранить хеши и достатчоно быстро сравнивать hash урла сравнить с hash урла. Может быть есть какие то готовые варианты? Или необходимо использовать другую базу данных?

Answer 1

[Антон]

tutunak И каждый из них я должен сравнить с 100 000 предыдущих (+ этот же файл будет увеличиваться с каждым появлением новых уникальных url).
Так-то в базах данных есть индексирование, они умеют строить деревья который оптимизируют поиск...
>>Появилась мысль, что можно сравнивать хеши этих строк.
Зачем писать велосипед если базы за вас это делают?

Comments

[tutunak]

т.е. мне просто создать таблицу в бд с n полей одно поле будет содержать url и по этому полю построить индекс? Дальше запросом определить есть ли в базе запись или нет?

Answer 2

[Алексей Милюта]

Прошу прощения, затупил конкретно. Все что было до этого не считается.
Если все данные в файле, то как я понимаю мы можем прочитать его с помощью следующего кода:
urls = open('urls.txt', 'r').read()
После того как мы его прочитаем нам его даже на массив строк разбивать не нужно. Есть замечательная функция find. Если строка найдена, то возвращает номер символа с которого начинается строка, если ее нет возвращает -1.
Весть код будет выглядеть так:

url = 'http://google.ru/'
urls = open('urls.txt', 'r').read()
find = urls.find(url)
if find==-1:
   urls.close()
   urls = open('urls.txt', 'w').write(url)
else:
   #тут код который вызываем при нахождении урла в базе.

Если url несколько, то их пилим в массив, и каждый ищем в базе, скорость поиска зашкаливает (если все правильно написать).

Answer 3

[Igor Nikolaev]

Судя по описанию, вам нужно сделать примитив в виде:

x = []
for i in data.split(" "):
    if i not in x:
        x.append(i)

Comments

[Roman K]

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

[Igor Nikolaev]

Roman Kitaev: можно, тут я указал, чтобы автору вопроса было понятно, что там может быть знак, принимаемый за разделитель.

[tutunak]

я не совсем понял как это мне поможет. У меня есть файл с 100 000 строк. каждая строка это уникальный url. При парсинге я получают N колличество (от 0 до 20) новых url . И каждый из них я должен сравнить с 100 000 предыдущих (+ этот же файл будет увеличиваться с каждым появлением новых уникальных url). Или сравнение будет достаточно в python? Нужно что бы все это отрабатывало в течении несколькоих секунд максимум. Вот поэтому я и задумался о сравнение хешей средствами базы данных. Ну либо я чего то не понимаю.

[tutunak]

* ли сравнение будет достаточно быстро работать в python?

[Igor Nikolaev]

а вы попробуйте, скорее всего скорости вам будет достаточно

[Артём Клименко]

tutunak: ээм, замените только в решении list на set, и проверка на вхождение ускориться порядка на три.
Если все данные помещаются в памяти, то такое решение будет максимально быстрым.