0

我有两个标记对象列表:

class Marker():
    def __init__(self,marker_number, marker_data):
        self.marker_number = marker_number
        self.marker_data = marker_data

我想做的是:

>>> existing_markers = [Marker(marker_number=1, marker_data= 'a'),
                     Marker(marker_number=2, marker_data= 'b'),
                     Marker(marker_number=3, marker_data= 'c'),
                     Marker(marker_number=4, marker_data= 'd'),
                     Marker(marker_number=5, marker_data= 'e'),]

>>> new_markers = [  Marker(marker_number=1, marker_data= 'aa'),
                     Marker(marker_number=3, marker_data= 'bb'),
                     Marker(marker_number=5,  marker_data= 'cc'),]

>>> interlace_markers(existing_markers, new_markers)

[Marker(marker_number=1, marker_data= 'a'),
Marker(marker_number=2, marker_data= 'aa'),
Marker(marker_number=3, marker_data= 'b'),
Marker(marker_number=4, marker_data= 'c'),
Marker(marker_number=5, marker_data= 'bb'),
Marker(marker_number=6, marker_data= 'd'),
Marker(marker_number=7, marker_data= 'e'),
Marker(marker_number=8,  marker_data= 'cc')]

因此,当我交错标记时,new_markers 列表中与原始标记列表具有相同编号的标记出现在原始标记之后,但编号会更新以保持编号序列。这是我目前的做法:

def interlace_markers(current_markers_list, new_markers_list):

    interlaced_markers = []
    #interlace the markers
    for existing_marker in current_markers_list:
        interlaced_markers.append(existing_marker)
        for new_marker in new_markers_list:
            if new_marker.marker_number== existing_marker.marker_number:
                interlaced_markers.append(new_marker)

    #reset the sequence
    sequence_index = 1
    for marker in interlaced_markers:
         marker.marker_number= sequence_index
         sequence_index += 1

    return interlaced_markers

我这里有两个问题:

  1. 什么是最pythonic的方式来做到这一点
  2. 原始列表可能很大~10k,并且是从外部文件创建的,但新列表会很小~100-300 长,有没有比使用列表更有效的方法呢?
4

1 回答 1

1

如果我理解正确,我认为这很容易通过简单的排序来完成:

interlace_markers = existing_markers + new_markers
interlace_markers.sort(key = lambda x: x.marker_number)

现在如果你想改变编号,你可以在一个简单的循环中做到这一点:

for i,marker in enumerate(interlace_markers):
    marker.marker_number = i+1 #indexing is 1 based instead of zero based

请注意,这是有效的,因为 python 的排序是稳定的,这意味着如果不必更改顺序,则不会更改。

这导致了 O(n) + O(nlogn) = O(nlogn) 算法,这还不错。

于 2012-08-16T14:29:11.637 回答