对列表中的元素子列表进行排序,其余部分保留在原位

Question

假设我有一个排序的字符串列表,如:

['A', 'B' , 'B1', 'B11', 'B2', 'B21', 'B22', 'C', 'C1', 'C11', 'C2']

现在我想基于Bs 的尾随数值进行排序- 所以我有:

['A', 'B' , 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'C1', 'C11', 'C2']

一种可能的算法是对正则表达式进行散列,例如regex = re.compile(ur'(B)(\d*))找到第一个和最后一个的索引B,对列表进行切片,使用正则表达式的第二个组对切片进行排序,然后插入已排序的切片.然而,这似乎太麻烦了.如果它与正则表达式不匹配并且只对匹配的项(子列表)进行排序,是否有办法编写一个"将项目保留在原位"的关键函数？

注意:以上只是一个例子 ; 我不一定知道模式(或者我也可能想要对C进行排序,或者任何具有尾随数字的字符串).理想情况下,我正在寻找一种解决一般问题的方法,即只对与给定标准匹配的子序列进行排序(或者失败,只是满足给定前缀的特定标准后跟一串数字的那些).

Answer 1

在简单的情况下,您只想以数字方式对尾随数字进行排序,并按字母顺序对非数字前缀进行排序,您需要一个键功能,将每个项目拆分为非数字和数字组件,如下所示:

'AB123' -> ['AB', 123]
'CD'    -> ['CD']
'456'   -> ['', 456]

注意:在最后一种情况下,空字符串''在CPython 2.x中并不是绝对必要的,因为整数在字符串之前排序 - 但这是一个实现细节而不是语言的保证,并且在Python 3.x中它是必要的,因为字符串和整数根本无法进行比较.

您可以使用列表推导构建这样的关键功能,并且re.split():

import re

def trailing_digits(x):
   return [
       int(g) if g.isdigit() else g
       for g in re.split(r'(\d+)$', x)
   ]

这是在行动:

>>> s1 = ['11', '2', 'A', 'B', 'B1', 'B11', 'B2', 'B21', 'C', 'C11', 'C2']

>>> sorted(s1, key=trailing_digits)
['2', '11', 'A', 'B', 'B1', 'B2', 'B11', 'B21', 'C', 'C2', 'C11']

一旦你添加了限制,只有具有特定前缀或前缀的字符串的尾随数字按数字排序,事情会变得复杂一些.

以下函数构建并返回满足要求的键函数:

def prefixed_digits(*prefixes):
    disjunction = '|'.join('^' + re.escape(p) for p in prefixes)
    pattern = re.compile(r'(?<=%s)(\d+)$' % disjunction)
    def key(x):
        return [
            int(g) if g.isdigit() else g
            for g in re.split(pattern, x)
        ]
    return key

这里的主要区别是创建了预编译的正则表达式(包含从提供的前缀或前缀构造的lookbehind),并返回使用该正则表达式的键函数.

以下是一些用法示例:

>>> s2 = ['A', 'B', 'B11', 'B2', 'B21', 'C', 'C11', 'C2', 'D12', 'D2']

>>> sorted(s2, key=prefixed_digits('B'))
['A', 'B', 'B2', 'B11', 'B21', 'C', 'C11', 'C2', 'D12', 'D2']

>>> sorted(s2, key=prefixed_digits('B', 'C'))
['A', 'B', 'B2', 'B11', 'B21', 'C', 'C2', 'C11', 'D12', 'D2']

>>> sorted(s2, key=prefixed_digits('B', 'D'))
['A', 'B', 'B2', 'B11', 'B21', 'C', 'C11', 'C2', 'D2', 'D12']

如果不带参数调用,则prefixed_digits()返回一个与trailing_digits以下行为相同的键函数:

>>> sorted(s1, key=prefixed_digits())
['2', '11', 'A', 'B', 'B1', 'B2', 'B11', 'B21', 'C', 'C2', 'C11']

注意事项:

1. 由于Python re模块中关于后瞻语法的限制,多个前缀必须具有相同的长度.

2. 在Python 2.x中,无论提供哪些前缀,纯数字字符串都将按数字排序prefixed_digits().在Python 3中,它们会引发异常(除非在没有参数的情况下调用,或者在特殊情况下调用key=prefixed_digits('')- 它将在数字上对纯数字字符串进行排序,并按字母顺序排列前缀字符串).使用更复杂的正则表达式修复可能是可能的,但是我在大约20分钟后放弃了尝试.

Answer 2

如果我理解正确的话,你的最终目标是对子序列进行排序,同时单独留下不属于子序列的项目.

在您的示例中,子序列定义为以"B"开头的项目.您的示例列表恰好包含字典顺序中的项目,这有点太方便了,并且可能会分散查找通用解决方案的注意力.让我们通过使用不同的示例列表来混合一些东西.怎么样:

['X', 'B2', 'B11', 'B22', 'B', 'B1', 'B21', 'C', 'Q1', 'C11', 'C2']

在这里,项目不再被订购(至少我试图组织它们,以便它们不是),既不是以"B"开头的,也不是其他的.然而,以"B"开头的项目仍然形成单个连续的子序列,占据单个范围1-6而不是分割范围,例如0-3和6-7.这又可能会分散注意力,我将进一步解决这个问题.

如果我正确理解您的最终目标,您希望此列表按如下方式排序:

['X', 'B', 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'Q1', 'C11', 'C2']

为了使这项工作,我们需要一个返回元组的键函数,这样:

• 第一价值:
  • 如果项目不以"B"开头,那么原始列表中的索引(或相同顺序的值)
  • 如果项目以"B"开头,那么最后一项不以"B"开头的索引
• 第二个价值:
  • 如果该项目不以"B"开头,则省略此项
  • 如果项目以"B"开头,则为数值

这可以像这样实现,有些doctests:

def order_sublist(items):
    """
    >>> order_sublist(['A', 'B2', 'B11', 'B22', 'B', 'B1', 'B21', 'C', 'C1', 'C11', 'C2'])
    ['A', 'B', 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'C1', 'C11', 'C2']

    >>> order_sublist(['X', 'B2', 'B11', 'B22', 'B', 'B1', 'B21', 'C', 'Q1', 'C11', 'C2'])
    ['X', 'B', 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'Q1', 'C11', 'C2']

    """
    def key():
        ord1 = [0]

        def inner(item):
            if not item.startswith('B'):
                ord1[0] += 1
                return ord1[0],
            return ord1[0], int(item[1:] or 0)
        return inner

    return sorted(items, key=key())

在此实现中,项目按以下键排序:

[(1,), (1, 2), (1, 11), (1, 22), (1, 0), (1, 1), (1, 21), (2,), (3,), (4,), (5,)]

由于关键元组中的第一个值,不以"B"开头的项目保持其顺序,并且由于关键元组的第二个值,以"B"开头的项目被排序.

这个实现包含一些值得解释的技巧:

• 该key函数返回1或2个元素的元组,如前所述:非B项有一个值,B项有两个.

• 元组的第一个值不完全是原始索引,但它足够好.第一个B项之前的值为1,所有B项使用相同的值,B之后的值每次都增加一个值.由于(1,) < (1, x) < (2,)哪里x可以是任何东西,这些键将按我们想要的那样排序.

现在谈到"真正的"伎俩:-)

• 什么与ord1 = [0]和ord1[0] += 1？这是一种更改函数中非本地值的技术.如果我使用简单ord1 = 0而ord1 += 1无法工作,因为它ord1是在函数之外定义的原始值.没有global关键字,它既不可见也不可重新分配.函数ord1内的原始值inner将遮蔽外部原始值.但ord1作为一个列表,它在内部可见inner,其内容可以修改.请注意,无法重新分配.如果替换ord1[0] += 1为ord1 = [ord1[0] + 1]导致相同值的as,则不起作用,因为在ord1左侧是局部变量,ord1在外部作用域中遮蔽,而不是修改其值.

• 这些key和inner功能有什么关系？如果我们传递给的关键功能sorted可以重复使用,我认为它会很简洁.这个更简单的版本也适用:

  def order_sublist(items):
      ord1 = [0]
  
      def inner(item):
          if not item.startswith('B'):
              ord1[0] += 1
              return ord1[0],
          return ord1[0], int(item[1:] or 0)
  
      return sorted(items, key=inner)
  

  重要的区别在于,如果您想要使用inner两次,两个用户将共享相同的ord1列表.这是可以接受的,因为整数值ord1[0]在使用期间不会溢出.在这种情况下,你不会使用该函数两次,即使你可能没有整数溢出的风险,但作为一个原则问题,通过包装它作为我使函数干净和可重用是很好的在我最初的提案中做了.该key函数的作用是简单地ord1 = [0]在其范围内初始化,定义inner函数并返回inner函数.ord1由于关闭,这种方式实际上是私密的.每次调用时key(),它都会返回一个具有私有新ord1值的函数.

• 最后但同样重要的是,请注意doctests:""" ... """评论不仅仅是文档,它是可执行测试.这些>>>行是在Python shell中执行的代码,以下行是预期的输出.如果您在一个名为的文件中有此程序script.py,则可以运行测试python -m doctest script.py.当所有测试通过时,您没有输出.当测试失败时,您会得到一个很好的报告.通过演示的示例,这是验证程序是否有效的好方法.您可以使用空白行分隔多个测试用例,以涵盖有趣的角落案例.在此示例中,有两个测试用例,包括原始排序输入和修改后的未排序输入.

然而,正如@ zero-piraeus发表了一篇有趣的评论:

我可以看到你的解决方案依赖于sorted()从左到右扫描列表(这是合理的 - 我无法想象TimSort将会很快被替换或彻底改变 - 但不能由Python AFAIK保证,并且有排序算法不能那样工作).

我试图自我批评,并怀疑从左到右的扫描是合理的.但我认为是.毕竟,排序确实是基于键而不是实际值发生的.我认为Python很可能是这样的:

1. 获取键值列表,[key(value) for value in input]从左到右访问值.
2. zip 包含原始项目的键列表
3. 在压缩列表上应用任何排序算法,通过zip的第一个值比较项目,并交换项目
4. 最后,返回已排序的项目 return [t[1] for t in zipped]

在构建键值列表时,它可以在多个线程上工作,比方说两个,第一个线程填充前半部分,第二个线程并行填充后半部分.这会弄乱这个ord1[0] += 1伎俩.但我怀疑它是否做了这种优化,因为它看起来有点矫枉过正.

但是为了消除任何疑问,我们可以自己遵循这个替代实施策略,尽管解决方案变得更加冗长:

def order_sublist(items):
    """
    >>> order_sublist(['A', 'B2', 'B11', 'B22', 'B', 'B1', 'B21', 'C', 'C1', 'C11', 'C2'])
    ['A', 'B', 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'C1', 'C11', 'C2']

    >>> order_sublist(['X', 'B2', 'B11', 'B22', 'B', 'B1', 'B21', 'C', 'Q1', 'C11', 'C2'])
    ['X', 'B', 'B1', 'B2', 'B11', 'B21', 'B22', 'C', 'Q1', 'C11', 'C2']

    """
    ord1 = 0
    zipped = []
    for item in items:
        if not item.startswith('B'):
            ord1 += 1
        zipped.append((ord1, item))

    def key(item):
        if not item[1].startswith('B'):
            return item[0],
        return item[0], int(item[1][1:] or 0)

    return [v for _, v in sorted(zipped, key=key)]

请注意,由于doctests,我们有一个简单的方法来验证替代实现仍然像以前一样工作.

如果您想要此示例列表,该怎么办

['X', 'B', 'B1', 'B11', 'B2', 'B22', 'C', 'Q1', 'C11', 'C2', 'B21']

要像这样排序:

['X', 'B', 'B1', 'B2', 'B11', 'B21', 'C', 'Q1', 'C11', 'C2', 'B22']

也就是说,以"B"开头的项目按其数值排序, 即使它们不形成连续的子序列？

使用神奇的按键功能是不可能的.但肯定有可能,还有更多的腿部工作.你可以:

1. 创建一个列表,其中包含以"B"开头的项目的原始索引
2. 创建一个包含以"B"开头的项目的列表,并按照您喜欢的方式对其进行排序
3. 在原始索引处回写已排序列表的内容

如果您需要最后一次实施的帮助,请告诉我.