Python优化词典列表之间的比较

6 回答

• 0

  （AFAICT，以下解决方案在算法上比到目前为止发布的任何其他答案更快：大约O（N log N）对O（N²） . 警告：这假设您在边界框之间没有大量重叠 . ）

  如果允许预先计算索引结构：

  • 将所有最小/最大x值推入集合并对其进行排序，从而创建跨越x轴的垂直区域列表 . 将每个区域与包含它的一组边界框相关联 .

  • 对min / max y值重复此过程，以创建水平区域列表，并将每个区域与其包含的边界框组相关联 .

  • 对于每个被测试的点：

  • 使用二进制印章查找包含点的x坐标的水平区域 . 但是，您真正想要的是与该区域相关联的一组边界框 .

  • 同样，找到与y坐标关联的一组边界框 .

  • 找到这两组的交集 .

  • 使用毕达哥拉斯测试此残留集中的边界框 .

  回复于 2024-04-29T03:47:21+08:00
• 1

  我们可以从样本中删除一个

  除非您需要按索引迭代列表，否则不应该使用范围，并将ifs合并在一起

  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']))
  

  回复于 2024-04-29T03:47:21+08:00
• 0

  接受了所有这些建议后，我设法提出了比原始解决方案快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（）而不是list提供了大量的加速 . 数据集越大（nx，ny，nz），加速越快 .

  它仍然可以使用树实现和域分解来改进，如同建议的那样，但目前它的工作原理 .

  感谢大家的建议！

  回复于 2024-04-29T03:47:21+08:00
• 3

  （这个答案涉及简单的优化和Python风格;它适用于现有算法，教授一些优化点，而不是用更有效的方法替换它 . ）

  以下是一些要点，以使代码更易于阅读和理解：

  • 迭代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 放在外部循环中以获得可能的轻微性能增益 . ）

  回复于 2024-04-29T03:47:21+08:00
• 1

  实际上，您可以通过以下方式保存所有内容：

  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
  

  回复于 2024-04-29T03:47:21+08:00
• 0

  首先，Python不是由低级语言教授的，它实际上更慢 . range(len(whatever)) 实际上创建了一个新的数字列表，然后您处理从该列表中传递给您的数字 . 你真正想做的就是使用从 whatever 交给你的物品 .

  在我们处理它的同时，我们可以拉出多次检查的公共 s['radius'] 位，并将边界框的所有if检查放在一行上 . 哦，我们不是't need a separate ' tmpRad ', and I assume the ' num已经是 int 并且不需要转换（如果它们确实如此，为什么？为什么不提前转换它们？）

  这些都不会产生差异，但它至少使它更容易阅读，并且绝对不会受到伤害 .

  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（3个布尔结果的8个组合） . 然后使用相同的标准 - 例如，每个都被切成8个 . 如果x / y / z的可能范围是-10..10，那么我们根据x> 5，y> 5，z> 5切割“x> 0，y> 0，z> 0”列表等等你明白了 .

  • 对于sList中的每个点，我们检查minx> 0等 . 漂亮的部分：如果minx> 0，我们不必检查任何'x <0'列表，如果maxx <0，我们不必检查任何'x> 0'列表 . 等等 . 我们弄清楚边界框与之相交的空间的8个“八分圆”中的哪一个;对于每一个，我们递归检查那些八分圆等的适当的八分圆，直到我们到达树的叶子，然后我们做正常的入点边框，然后进行点球测试 .

  回复于 2024-04-29T03:47:21+08:00