Подобная массиву структура данных, эффективная с точки зрения вставки и поиска времени

Question

Мне нужна структура данных, реализованная на языке Ruby, для размещения огромного количества различных URL-адресов (например, 10**10 штук), поэтому производительность - моя забота. Я использую Array и сохраняю его элементы упорядоченными, чтобы я мог выполнить binary search, чтобы найти, если он уже существует или где быстро вставить URL. Я написал это:

class UrlStore
    def initialize(*args)
        @urls = []
        args.each { |e| add(e) unless e.class != String }
    end

    def add(url)
        p = find(url)
        @urls.insert(p, url) unless p.class == String
    end


    def find(url)
        l, m, h = 0, 0, @urls.size - 1

        while l <= h do
            m = l + (h - l) / 2
            b = url <=> @urls[m]
            if b == 0
                return m.to_s
            elsif b == 1
                l = m + 1
            else
                h = m - 1
            end
        end

        return l
    end
end

Метод find, если он найден, возвращает позицию URL в массиве хостинга, но в форме String, чтобы отличать его от тех позиций, которые были найдены для вставки; В противном случае, верните целое число (Fixnum), указывающее, куда должен идти URL, чтобы сохранить порядок в массиве.

Но учтите, что я использую Array#insert, чтобы добавить элемент в указанной позиции. Моя интуиция подсказывает мне, что этот метод переместит все элементы после вставки и сделает шаг назад, что может привести к серьезному снижению производительности. Модуль Array отсутствует в стандартной библиотеке, это свойственный тип данных Ruby, поэтому я не знаю, прав ли я.

Может быть, это настолько наивная структура данных для размещения такой задачи. Так что любой может поделиться удивительным.

Answer 1

Если, как предположил Phrogz, вам удастся получить 370 ГБ памяти или вы понимаете, что на самом деле вам не нужно хранить такое количество URL-адресов, вы можете захотеть использовать SortedSet .

Answer 2

Возможно, вы захотите взглянуть на растущее число решений NoSQL с открытым исходным кодом, включая MongoDB, Cassandra, Kyoto Cabinet или Redis.

MongoHQ предоставляет бесплатный хостинг для MongoDB. RedisToGo предоставляет бесплатный хостинг для Redis. Оба имеют очень простые в использовании рубиновые привязки. Я использовал оба и рекомендую их.

Я слышал хорошие вещи о Кассандре и Киотском Кабинете, но не использовал их ни в одном производственном приложении.