将排列应用于列表的原位方法？(按键排序的反转)

Question

这是我想要做的一个例子

spam_list = ["We", "are", "the", "knights", "who", "say", "Ni"]
spam_order = [0,1,2,4,5,6,3]
spam_list.magical_sort(spam_order)
print(spam_list)

["We", "are", "the", "who", "say", "Ni", "knights"]

我可以用enumerate,list等等,但我想直接影响spam_list,喜欢list.sort()和不复制它sorted()

编辑:推送一个字符串示例,以避免索引和值之间的混淆spam_list

编辑:原来这是Python排序并行数组的副本吗？.好吧,我不能删除SO一致性论点的那么多努力.

Answer 1

你可以尝试:

spam_list = [spam_list[i] for i in spam_order]

Answer 2

你可以给keysort函数赋一个特殊的东西:

order = dict(zip(spam_list, spam_order))
spam_list.sort(key=order.get)

编辑:正如@ninjagecko在他的回答中指出的那样,这并不是很有效,因为它复制了两个列表以创建查找字典.但是,通过OP给出的修改示例,这是唯一的方法,因为必须构建一些索引.好处是,至少对于字符串,值不会被复制,因此开销只是字典本身的开销.

Answer 3

但是我想直接影响spam_list,比如list.sort()而不是像sorted()那样复制它

只有一个解决方案,完全符合您的要求.每个其他解决方案都隐含地制作一个或两个列表的副本(或将其转换为字典等).您要求的是一种方法,使用O(1)额外的空间对两个列表进行排序,使用一个列表作为另一个列表的键.我个人会接受额外的空间复杂性,但如果你真的想要,你可以这样做:

(编辑:可能是原始海报并不真正关心的情况,.sort因为它是有效的,而是因为它修改了状态;一般来说,这是一个危险的东西,而非低级语言试图避免这种情况和甚至禁止它,但使用切片分配的解决方案将实现"就地"语义)

• 创建一个自定义字典子类(实际上是一个Zip类),它由您正在排序的两个列表支持.
• 索引myZip[i]- >结果是元组(list1[i],list2[i])
• 作业myZip[i]=(x1,x2)- >发送到list1[i]=x1, list2[i]=x2.
• 使用该做myZip(spam_list,spam_order).sort()的,现在都spam_list和spam_order排序就地

例:

#!/usr/bin/python3

class LiveZip(list):
    def __init__(self, list1, list2):
        self.list1 = list1
        self.list2 = list2

    def __len__(self):
        return len(self.list1)

    def __getitem__(self, i):
        return (self.list1[i], self.list2[i])

    def __setitem__(self, i, tuple):
        x1,x2 = tuple
        self.list1[i] = x1
        self.list2[i] = x2

spam_list = ["We", "are", "the", "knights", "who", "say", "Ni"]
spam_order = [0,1,2,4,5,6,3]

#spam_list.magical_sort(spam_order)
proxy = LiveZip(spam_order, spam_list)

现在让我们看看它是否有效......

#proxy.sort()
#fail --> oops, the internal implementation is not meant to be subclassed! lame
# It turns out that the python [].sort method does NOT work without passing in
# a list to the constructor (i.e. the internal implementation does not use the
# public interface), so you HAVE to implement your own sort if you want to not
# use any extra space. This kind of dumb. But the approach above means you can 
# just use any standard textbook in-place sorting algorithm:
def myInPlaceSort(x):
    # [replace with in-place textbook sorting algorithm]

它现在有效:

myInPlaceSort(proxy)

print(spam_list)

不幸的是,没有办法只在O(1)空间中排序一个列表而不对其他列表进行排序 ; 如果您不想对两个列表进行排序,那么您可以使用构建虚拟列表的原始方法.

但是,您可以执行以下操作:

spam_list.sort(key=lambda x:x)

但是如果key或cmp函数对任何集合进行任何引用(例如,如果你传入一个dict.__getitem__你必须构造的dict),这并不比你的原始O(N)空间方法更好,除非你已经碰巧有这样一个字典.

原来这是Python排序并行数组的重复问题吗？,但这个问题也没有正确的答案,除了这个,这相当于我的,但没有示例代码.除非您拥有令人难以置信的优化或专业代码,否则我只会使用您的原始解决方案,这在空间复杂性方面与其他解决方案相当.

edit2:正如发送者指出的那样,OP根本不想要排序,而是希望,我认为,应用排列.要实现这一点,您可以并且应该使用其他答案建议的简单索引[spam_list[i] for i in spam_order],但必须仍然需要显式或隐式复制,因为您仍然需要中间数据.(无关,并作记录,运用逆置换是我认为并行排序的倒数与身份,您可以使用一个拿到另一方面,虽然排序是更短的时间效率._,spam_order_inverse = parallelSort(spam_order, range(N)),然后排序spam_order_inverse,我离开上述关于整理记录的讨论.)

EDIT3:

然而,有可能在O(#cycles)空间中实现就地排列,但具有可怕的时间效率.每个排列都可以分解为在子集上并行应用的不相交排列.这些子集称为循环或轨道.期间等于它们的大小.你这样做了一个信念的飞跃,做如下:

Create a temp variable.

For index i=0...N:
    Put x_i into temp, assign NULL to x_i
    Swap temp with x_p(i)
    Swap temp with x_p(p(i))
    ...
    Swap temp with x_p(..p(i)..), which is x_i
    Put a "do not repeat" marker on the smallest element you visited larger than i
    Whenever you encounter a "do not repeat" marker, perform the loop again but
      without swapping, moving the marker to the smallest element larger than i    
    To avoid having to perform the loop again, use a bloom filter

这将在O(N ^ 2)时间和O(#cycles)位置运行,没有布隆过滤器,或~O(N)时间和O(#cycle + bloomfilter_space)空间如果你使用它们