Оптимизированное сравнение Python между списком Dict

Question

Я пытаюсь проверить, находятся ли узлы в объеме сферы и добавляет идентификатор узла в список. Однако эффективность алгоритма невероятно медленная, и я не уверен, как ее улучшить.

У меня есть два списка. Список A имеет формат [{'num': ID, 'x': VALUE, 'y': VALUE, 'z': VALUE], тогда как список B имеет формат [{'x': VALUE, 'y ': VALUE,' z ': VALUE,' rad ': VALUE}].

Размер обоих списков может превышать 100 000 предметов каждый.

Мой текущий код опубликован ниже, но он очень неэффективен.

filteredList = [] 
    for i in range(len(sList)): 

      minx = (sList[i]['x']) - (sList[i]['radius']) 
      maxx = (sList[i]['x']) + (sList[i]['radius']) 
      miny = (sList[i]['y']) - (sList[i]['radius']) 
      maxy = (sList[i]['y']) + (sList[i]['radius']) 
      minz = (sList[i]['z']) - (sList[i]['radius']) 
      maxz = (sList[i]['z']) + (sList[i]['radius']) 

      for j in range(len(nList)): 
        if minx <= nList[j]['x'] <= maxx: 
          if miny <= nList[j]['y'] <= maxy: 
            if minz <= nList[j]['z'] <= maxz: 
              tmpRad = findRadius(sList[i],nList[j]) 
              if tmpRad <= sList[i]['radius']: 
                filteredList.append(int(nList[j]['num'])) 

Я в недоумении и ценю любые идеи.

Редактировать: Добавление дополнительной информации о формате data.

Список А (NLIST) - определяет узлы, с места х, у, z, и идентификатор NUM
[{ 'у': 0,0, 'х': 0,0, 'Num': 1,0 ' z ': 0.0},
{' y ': 0.0,' x ': 1.0,' num ': 2.0,' z ': 0.0},
{' y ': 0.0,' x ': 2.0,' num ': 3.0,' z ': 0.0},
{' y ': 0.0,' x ': 3.0,' num ': 4.0,' z ': 0.0},
{' y ': 0.0,' x ': 4.0,' num ': 5.0,' z ': 0.0},
{' y ': 0.0,' x ': 5.0,' num ': 6.0,' z ': 0.0},
{' y ': 0.0,' x ': 6.0,' num ': 7.0,' z ': 0.0},
{'y': 0.0, 'x': 7.0, 'num': 8.0, 'z': 0.0},
{'y': 0.0, 'x': 8.0, 'num': 9.0, ' г ': 0,0}, {
' у ': 0,0, 'х': 9,0, 'Num': 10,0, 'Z': 0,0}]

список B (SLIST) - определяет сферы, используя x, y, z, радиус
[{'y': 18.0, 'x': 25.0, 'z': 26.0, 'radius': 0,0056470000000000001},
{'y': 29.0, 'x': 23.0 , 'z': 45,0, 'radius': 0,0066280000000000002},
{'y': 46.0, 'x': 29.0, 'z': 13.0, 'radius': 0.014350999999999999},
{'y': 0 , 0, 'x': 20.0, 'z': 25.0, 'radius': 0.014866000000000001},
{'y': 27.0, 'x': 31.0, 'z': 18.0, 'radius': 0.018311999999999998},
{'y': 10.0, 'x': 36.0, 'z': 46.0, 'radius': 0.024702000000000002},
{'y': 27.0, 'x': 13.0, 'z': 48.0, 'radius ': 0.027300999999999999},
{' y ': 14.0,' x ': 1.0,' z ': 13.0,' radius ': 0.033889000000000002},
{' y ': 31.0,' x ': 20.0,' z ': 11.0,' radius ': 0.034118999999999997},
{' y ': 23.0,' x ': 28.0,' z ': 8.0,' radius ': 0.036683}]

Answer 1

Принимая во внимание все эти рекомендации, мне удалось найти решение, которое было примерно в 50 раз быстрее оригинала.

Я понял, что узкое место было в типе данных (список dicts), который я использовал. Переключение по нескольким спискам было невероятно медленным в моем приложении, а использование наборов было намного более эффективным.

Первое, что я сделал, это реализовать именованные кортежи. Я знал, что мой список узлов пронумерован, что обеспечило хэш, который мне нужен для повышения эффективности.

def findNodesInSpheres(sList,nList,nx,ny,nz): 
    print "Running findNodesInSpheres" 
    filteredList = [] 
    for a in sList: 
      rad = a.radius 
      minx = (a.x) - (rad) if (a.x - rad > 0) else 0 
      maxx = (a.x) + (rad) if (a.x + rad < nx) else nx 
      miny = (a.y) - (rad) if (a.y - rad > 0) else 0 
      maxy = (a.y) + (rad) if (a.y + rad < ny) else ny 
      minz = (a.z) - (rad) if (a.z - rad > 0) else 0 
      maxz = (a.z) + (rad) if (a.z + rad < nz) else nz 
      boundingBox = set([ (i + j * (nx + 1) + k * (nx + 1) * (ny + 1)) for i in range (int(minx),int(maxx)+1) 
          for j in range (int(miny),int(maxy)+1) for k in range(int(minz),int(maxz)+1) ]) 

      for b in sorted(boundingBox): 
        if findRadius(a,nList[b]) <= rad: 
          filteredList.append(nList[b].num) 
    return filteredList 

Использование set() вместо списка дает массивные ускорения. Чем больше набор данных (nx, ny, nz), тем больше ускорение.

Его можно было бы улучшить с помощью реализации дерева и декомпозиции домена, как было предложено, но на данный момент это работает.

Спасибо всем за советы!

Answer 2

один можно удалить из образца

, если вам не нужно перебирать список по индексу, не следует также избегать использования диапазона, и объединить сослагательное наклонение вместе

filteredList = [] 
for a in sList: 

     minx = (a['x']) - (a['radius']) 
     maxx = (a['x']) + (a['radius']) 
     miny = (a['y']) - (a['radius']) 
     maxy = (a['y']) + (a['radius']) 
     minz = (a['z']) - (a['radius']) 
     maxz = (a['z']) + (a['radius']) 

     for b in nList: 
       if minx <= b['x'] <= maxx and miny <= b['y'] <= maxy and minz <= b['z'] <= maxz: 
        tmpRad = findRadius(a,b) 
        if tmpRad <= a['radius']: 
         filteredList.append(int(b['num'])) 

Answer 3

(Этот ответ касается простых оптимизаций и стиля Python, он работает с существующим алгоритмом, обучая некоторым точкам оптимизации, а не заменяя его более эффективным.)

Вот несколько моментов, чтобы начать код легче читать и понимать d:

• Итерации по sList, а не по диапазону (len (sList)). for i in range(len(sList)) будет for i in sList и sList[i] будет i.

• Нет необходимости в этом tmpRad; поместите его в линию.

• Вместо if a: if b: if c:if a and b and c.

Теперь мы на это:

filteredList = [] 
for i in sList: 
    minx = i['x'] - i['radius'] 
    maxx = i['x'] + i['radius'] 
    miny = i['y'] - i['radius'] 
    maxy = i['y'] + i['radius'] 
    minz = i['z'] - i['radius'] 
    maxz = i['z'] + i['radius'] 

    for j in nList: 
     if minx <= j['x'] <= maxx and miny <= j['y'] <= maxy and minz <= j['z'] <= maxz and findRadius(i,j) <= i['radius']: 
      filteredList.append(int(j['num'])) 

(PEP 8 рекомендовал бы расщеплению, что длинная линия для линий не более 80 символов; PEP 8 также будет рекомендовать filtered_list и s_list и n_list скорее чем filteredList, sList и nList.)

---

Я поставил findRadius(i, j) <= i['radius'] сначала для стиля и потому, что похоже, что более вероятно, что он будет оценивать значение false, ускоряя вычисления. Тогда я также встраиваются в minx и т.д. переменные:

filteredList = [] 
for i in sList: 
    for j in nList: 
     if findRadius(i, j) <= i['radius'] \ 
     and i['x'] - i['radius'] <= j['x'] <= i['x'] + i['radius'] \ 
     and i['y'] - i['radius'] <= j['y'] <= i['y'] + i['radius'] \ 
     and i['z'] - i['radius'] <= j['z'] <= i['z'] + i['radius']: 
      filteredList.append(int(j['num'])) 

Одна вещь, чтобы думать о том, что i['x'] - i['radius'] <= j['x'] <= i['x'] + i['radius'] может быть упрощена; попробуйте такие вещи, как вычитание i['x'] из всех трех частей.

Вы можете укоротить это еще раз со списком.

filteredList = [int(j['num']) for j in nList for i in sList 
     if findRadius(i, j) <= i['radius'] 
     and i['x'] - i['radius'] <= j['x'] <= i['x'] + i['radius'] 
     and i['y'] - i['radius'] <= j['y'] <= i['y'] + i['radius'] 
     and i['z'] - i['radius'] <= j['z'] <= i['z'] + i['radius']] 

И, наконец, named tuples (это имеет побочный эффект: они неизменны, тоже, что, вероятно, желательно? Также обратите внимание, что это Python 2.6, прочтите страницу для того, как вы могли бы сделать это с более старыми версиями Python):

from collections import namedtuple 

node = namedtuple('node', 'x y z num') 
sphere = namedtuple('sphere', 'x y z radius') 

nList = [ 
     node(x=0.0, y=0.0, z=0.0, num=1.0), 
     node(x=1.0, y=0.0, z=0.0, num=2.0), 
     node(x=2.0, y=0.0, z=0.0, num=3.0), 
     node(x=3.0, y=0.0, z=0.0, num=4.0), 
     node(x=4.0, y=0.0, z=0.0, num=5.0), 
     node(x=5.0, y=0.0, z=0.0, num=6.0), 
     node(x=6.0, y=0.0, z=0.0, num=7.0), 
     node(x=7.0, y=0.0, z=0.0, num=8.0), 
     node(x=8.0, y=0.0, z=0.0, num=9.0), 
     node(x=9.0, y=0.0, z=0.0, num=10.0)] 

sList = [ 
     sphere(x=25.0, y=18.0, z=26.0, radius=0.0056470000000000001), 
     sphere(x=23.0, y=29.0, z=45.0, radius=0.0066280000000000002), 
     sphere(x=29.0, y=46.0, z=13.0, radius=0.014350999999999999), 
     sphere(x=20.0, y=0.0, z=25.0, radius=0.014866000000000001), 
     sphere(x=31.0, y=27.0, z=18.0, radius=0.018311999999999998), 
     sphere(x=36.0, y=10.0, z=46.0, radius=0.024702000000000002), 
     sphere(x=13.0, y=27.0, z=48.0, radius=0.027300999999999999), 
     sphere(x=1.0, y=14.0, z=13.0, radius=0.033889000000000002), 
     sphere(x=20.0, y=31.0, z=11.0, radius=0.034118999999999997), 
     sphere(x=28.0, y=23.0, z=8.0, radius=0.036683)] 

Тогда вместо sphere['radius'] вы можете сделать sphere.radius.Это делает код аккуратнее:

filteredList = [int(j.num) for j in nList for i in sList 
     if findRadius(i, j) <= i.radius 
     and i.x - i.radius <= j.x <= i.x + i.radius 
     and i.y - i.radius <= j.y <= i.y + i.radius 
     and i.z - i.radius <= j.z <= i.z + i.radius] 

Или, без списка понимания,

filteredList = [] 
for i in sList: 
    for j in nList: 
     if findRadius(i, j) <= i.radius \ 
     and i.x - i.radius <= j.x <= i.x + i.radius \ 
     and i.y - i.radius <= j.y <= i.y + i.radius \ 
     and i.z - i.radius <= j.z <= i.z + i.radius: 
      filteredList.append(int(j.num)) 

Наконец, выбрать более хорошие имена; [Стиль немного изменился за комментариями, поставив findRadius в конце, как это более вероятно, будет вычислительно дорогой - ты самый лучший судья, что, хотя]

filteredList = [int(n.num) for n in nodes for s in spheres 
     if s.x - s.radius <= n.x <= s.x + s.radius and 
      s.y - s.radius <= n.y <= s.y + s.radius and 
      s.z - s.radius <= n.z <= s.z + s.radius and 
      findRadius(s, n) <= s.radius] 

Или,

filteredList = [] 
for s in spheres: 
    for n in nodes: 
     if (s.x - s.radius <= n.x <= s.x + s.radius and 
      s.y - s.radius <= n.y <= s.y + s.radius and 
      s.z - s.radius <= n.z <= s.z + s.radius and 
      findRadius(s, n) <= s.radius): 
      filteredList.append(int(n.num)) 

(Вы можете поставить srad = s.radius во внешний контур для возможного небольшого увеличения производительности, если это необходимо.)

Answer 4

Прежде всего, Python не построен для такого рода итераций. Использование индексов для каждого элемента списка - назад, своего рода повреждение мозга, которое обучается низкоуровневым языкам, где он быстрее. В Python это на самом деле медленнее. range(len(whatever)) фактически создает новый список чисел, а затем вы работаете с номерами, которые вам переданы из этого списка. То, что вы действительно хотите сделать, это просто работать с объектами, которые вам переданы от whatever.

Пока мы находимся на нем, мы можем вытащить обычный бит s['radius'], который проверяется несколько раз, и поместить все проверки if в ограничительную рамку на одну строку. О, и нам не нужен отдельный «tmpRad», и я предполагаю, что «num» уже int s и их не нужно преобразовывать (если они это делают, почему? Почему бы просто не переделать их раньше времени?)

Все это сделает огромным различий, но это по крайней мере упрощает чтение и, безусловно, не болит.

filteredList = [] 
for s in sList: 
    radius = s['radius'] 
    minx = s['x'] - radius 
    maxx = s['x'] + radius 
    miny = s['y'] - radius 
    maxy = s['y'] + radius 
    minz = s['z'] - radius 
    maxz = s['z'] + radius 

    for n in nList: 
    if (minx <= n['x'] <= maxx) and (miny <= n['y'] <= maxy) and \ 
     (minz <= n['z'] <= maxz) and (findRadius(s, n) <= radius): 
     filteredList.append(n['num']) 

Теперь, по крайней мере, ясно, что происходит.

Однако в масштабах проблемы, с которой мы работаем, похоже, что нам потребуются алгоритмические улучшения. То, что вы, вероятно, захотите сделать здесь, - это использование какой-то техники BSP (двоичного разделения пространства). Как это работает:

• Во-первых, мы переставляем nList в дерево. Мы разбиваем его на 8 меньших списков, основываясь на x> 0, независимо от того, y> 0 и z> 0 для каждой точки (8 комбинаций из 3 булевых результатов). Затем каждый из них снова разрезается на 8, используя одни и те же критерии - например, если возможный диапазон для x/y/z равен -10..10, то мы вырезаем список «x> 0, y> 0, z> 0» в зависимости от того, х> 5, y> 5, z> 5 и т. д. Вы получаете идею.

• Для каждой точки sList мы проверяем, являются ли minx> 0 и т. Д. Прекрасная часть: если minx> 0, нам не нужно проверять какие-либо из «x < 0», а если maxx < 0, нам не нужно проверять список «x> 0». И так далее. Мы выясним, из какого из восьми «октантов» пространства ограничивается прямоугольник; и для каждого из них мы рекурсивно проверяем соответствующие октанты этих октантов и т. д. до тех пор, пока не дойдем до листьев дерева, а затем мы выполним обычную проверку в ящике, а затем в очках.

Answer 5

На самом деле, вы можете сохранить все что:

filteredList = [int(node['num']) for sphere in sList \ 
    for node in nList if findRadius(sphere,node)<=sphere['radius']] 

Если расстояние от точки до земного шара сферы меньше радиуса сферы, то я думаю, мы можем сказать, что это в сферы, правильно?

Я предполагаю, что findRadius определяется как:

def findRadius(sphere,node): 
    return ((node['x']-sphere['x'])**2 + \ 
      (node['y']-sphere['y'])**2 + \ 
      (node['z']-sphere['z'])**2)**.5 

Answer 6

(AFAICT, следующее решение алгоритмический быстрее, чем любой другой ответ, публикуемого до сих пор: приблизительно O (N журнала N) против O (N . ²) Оговорка: это предполагает, что вы не имеете огромное количество перекрытия между ограничивающими коробками)

Если вам разрешено предварительно вычислить структуру индекса:.

1. Вставьте все значения min/max x в набор и отсортируйте их, создав таким образом список вертикальных областей, охватывающих ось x. Свяжите каждую область с набором ограничивающих прямоугольников, которые ее содержат.
2. Повторите эту процедуру для значений min/max y, чтобы создать список горизонтальных областей и привяжите каждую область к набору ограничивающих полей, которые она содержит.
3. Для каждой проверяемой точки:
   • Используйте бинарную отбивку, чтобы найти горизонтальную область, содержащую координату x точки. Однако, что вы действительно хотите, это набор ограничивающих прямоугольников, связанных с областью.
   • Аналогичным образом найдите набор ограничивающих прямоугольников, связанных с координатой y.
   • Найти перекресток этих двух наборов.
4. Испытание ограничивающих коробок в этом наборе остатков с использованием Pythagoras.