Создание словаря из 700 тыс. Элементов в Python?

Question

У меня есть класс с именем Point, который имеет только x_coordinate и y_coordinate с плавающей точкой в ​​качестве своих атрибутов. У меня есть около 700000 объектов Point, которые я хотел бы сохранить в словаре.

Ключи словаря - это Point объекты, а соответствующие значения - Region объектов, которые содержат в себе около тысячи точек. По сути, ключ p принадлежит значению r, означающему, что точечный объект принадлежит конкретному объекту региона.

Короче говоря, это примитивный цикл, который я пытаюсь выполнить:

look_up_table = {}
for region in all_regions_list:
    for point in region.points_list:
        look_up_table[point] = region

Во всех регионах есть около 700000 объектов Point, уже загруженных в память. Таким образом, четвертая строка в коде, вероятно, будет выполнена 700 000 раз, а в словаре будет около 700 000 пар (ключ, значение).

Скажем, каждый объект Point занимает 1 КБ памяти (что на самом деле невозможно), а 700 000 точек занимают около 680 МБ. И у меня есть более 3 ГБ свободной оперативной памяти. Более того; эти объекты Point и Region уже загружены в память ...

Тем не менее, эти простые 4 строки занимают целую вечность, я ждал около 2 часов и не повезло ... Требуется около часа, чтобы хэшировать только 10k объектов ...

Итак, мой вопрос: я что-то не так делаю? Есть ли другой способ сохранить 700 тыс. Объектов в памяти и найти определенный ключ за O (1) раз?

Кстати, ниже приведены переопределенные методы класса Point:

def __hash__(self, *args, **kwargs):
        """ overriden hash method """
        hashcode = 133
        hashcode = hashcode * 23 + self.x_coordinate
        hashcode = hashcode * 23 + self.y_coordinate
        return hashcode

def __eq__(self, other):
    """ overriden equals method """
    if not other:
        return False
    else:
        return self.__cmp__(other) == 0

def __cmp__(self, other):
    """ overriden compare method """
    if other is not None:
        origin = Point(0.0, 0.0)
        if self.distance_between(origin) < other.distance_between(origin):
            return - 1
        elif self.distance_between(origin) > other.distance_between(origin):
        return 1
        else:
            return 0

Заранее спасибо ...

Answer 1

В вашем коде есть хотя бы одна ошибка - вероятно, не вызывающая проблем с производительностью, но на которую стоит обратить внимание. Существует одно требование, которое __hash__() метод должен выполнить согласно документации Python :

Единственным обязательным свойством является то, что объекты, которые сравниваются равными, имеют одинаковое значение хеш-функции; Рекомендуется каким-либо образом смешивать (например, используя exclusive или) хеш-значения для компонентов объекта, которые также играют роль в сравнении объектов.

С вашими определениями методов вполне возможно, что два сравниваемых объекта имеют разные хэши.

Answer 2

Почему бы не использовать простой (x, y) кортеж для ваших очков? Или namedtuple. Это будет намного быстрее.

Answer 3

Ваша __hash__ функция - очень плохой выбор хеша.Попробуйте полностью удалить эту функцию и посмотрите, работает ли хэш-функция по умолчанию лучше.

Кроме того, ваша __cmp__ функция довольно неэффективна, поскольку она будет вызывать distance_between четыре раза для при каждом сравнении.,Попробуйте предварительно вычислить для каждого Point расстояние между этой точкой и началом координат и сохранить его внутри объекта Point.Тогда __cmp__ может быть что-то вроде:

def __cmp__(self, other):
    return other.distance_to_origin - self.distance_to_origin

Answer 4

ОК, я «поздний ответчик», поэтому:

Проблемы с __hash__ и __eq__, как здесь используются, хорошо освещены.Я бы сказал, что Named tuple - это огромный звук в исполнении здесь.Следующим самым быстрым усилением (в основном по размеру) будет использование __slots__.Мертвый путь - это когда вы идентифицируете, что точка имеет «только» два атрибута.

В зависимости от фактических шаблонов использования, я бы, вероятно, либо:вы создаете точки и регионы одновременно.Тогда Point «знает», что она «родительская» .... (например, return self.region в Point)

namedtuples должен ускорить решение этой проблемы размера, но если вам нужно масштабировать на большие числа, вы всегда можетеобманывать и использовать sqlite3 (в памяти или нет) или другую библиотеку dbm и позволить кому-то еще беспокоиться о том, как бесконечно масштабировать размер

Answer 5

Комментарии к этому коду:

1. Поскольку ваши методы имеют фиксированное количество аргументов (например, def __eq__(self, other):), вам не нужно проверять, является ли other NoneВам нужно сделать это, только если у вас есть дополнительные аргументы.

2. Ваш метод __cmp__ является подозрительным.Вы не показываете определение distance_between, но подразумеваете, что это евклидова норма этой точки;т.е. расстояние от x, y до начала координат 0,0.Напомним, что евклидова норма точки 3,4 совпадает с точкой 4,3.Действительно ли они означают одну и ту же точку в логике вашей программы, хотя точка x = 3 и y = 4 - это точка, отличная от точки x = 4 и y = 3?

3. Вы сказали, что каждый регион имеет 1000 баллов.Вы сказали, что есть 700 000 баллов.Поскольку в каждом регионе около 1000 точек, должно быть около 700 регионов.Для простоты я буду использовать это вместо репликации класса Region.

Итак, рассмотрим следующее:

import random
import math

size=100

class Point(object):
    def __init__(self,x=0.0,y=0.0):
        self.x=x
        self.y=y

    def __hash__(self):
        t=(self.x,self.y)
        return hash(t)

    def __eq__(self, other):
        return self.__cmp__(other) == 0

    def distance_to_origin(self):
        return math.hypot(self.x,self.y)

    def __cmp__(self, other):
        return other.distance_to_origin() - self.distance_to_origin()

look_up_table = {}
for i in range(0,700):
    for j in range(0,1000):
        x=Point(random.uniform(-size,size),random.uniform(-size,size))
        look_up_table[x]=i

print len(look_up_table), "hash points with ",size*2," range"

В примере кода реализован более быстрый __hash__ на основе кортежа его составных частей.На моей машине этот словарь составляется за 3 или 4 секунды.

Как уже говорилось, ваша логика (которую я только что упростил) на __cmp__ может быть ошибочной:

x=Point(1.0,2.0)
y=Point(1.0,2.0)
z=Point(2.0,1.0)
a=Point(2.2,1.1)

print "x=y?", x==y    # as expected...
print "x=a?", x==a    # also
print "x=z?", x==z    # is that what you expect?

Даже если Point(1.0,2.0) == Point(2.0,1.0), потому что они имеют одинаковое расстояние до Point(0,0)hash(1.0,2.0) != hash(2.0,1.0).В результате у вас будет два объекта, которые сравнивают один и тот же хэшированный объект с разными объектами.

Answer 6

Рассматривали ли вы использование Numpy массивов?Одиночные отдельные элементы являются однородными, а не накладными расходами отдельных объектов Python.Намного быстрее и эффективнее с точки зрения памяти.