整数列表到范围

Question

我需要将ints列表转换为包含列表中所有范围的字符串。 因此，例如，输出应该是如下：

getIntRangesFromList([1,3,7,2,11,8,9,11,12,15]) -> "1-3,7-9,11-12,15" 

所以输入未排序并且可以有重复的值。这些列表的大小范围从一个元素到4k个元素。最小值和最大值分别为1和4094.

这是性能关键代码片的一部分。我一直在试图优化这一点，但我找不到一种更快的方法。这是我现在的代码：

def _getIntRangesFromList(list): 
    if (list==[]): 
     return '' 
    list.sort() 
    ranges = [[list[0],list[0]]] # ranges contains the start and end values of each range found 
    for val in list: 
     r = ranges[-1] 
     if val==r[1]+1: 
      r[1] = val 
     elif val>r[1]+1: 
      ranges.append([val,val]) 
    return ",".join(["-".join([str(y) for y in x]) if x[0]!=x[1] else str(x[0]) for x in ranges]) 

关于如何更快地获得这个的任何想法？

Answer 1

这可能是itertools模块的一项任务。

import itertools 

list_num = [1, 2, 3, 7, 8, 9, 11, 12, 15] 
groups = (list(x) for _, x in 
      itertools.groupby(list_num, lambda x, c=itertools.count(): x - next(c))) 
print(', '.join('-'.join(map(str, (item[0], item[-1])[:len(item)])) for item in groups)) 

这会给你1-3, 7-9, 11-12, 15。

要了解发生了什么，您可能需要检查groups的内容。

import itertools 
list_num = [1, 2, 3, 7, 8, 9, 11, 12, 15] 

groups = (list(x) for _, x in 
      itertools.groupby(list_num, lambda x, c=itertools.count(): x - next(c))) 
for element in groups: 
    print('element={}'.format(element)) 

这会给你以下输出。

element=[1, 2, 3] 
element=[7, 8, 9] 
element=[11, 12] 
element=[15] 

基本思路是让一个计数器与数字平行。 groupby将为与计数器的当前值具有相同数字距离的数字创建单个组。

我不知道你的Python版本是否更快。你必须自己检查一下。在我的设置中，使用这个数据集的速度会更慢，但更快速，更多的元素。

Answer 2

def _to_range(l, start, stop, idx, result): 
    if idx == len(l): 
     result.append((start, stop)) 
     return result 
    if l[idx] - stop > 1: 
     result.append((start, stop)) 
     return _to_range(l, l[idx], l[idx], idx + 1, result) 
    return _to_range(l, start, l[idx], idx + 1, result) 

def get_range(l): 
    if not l: 
     return [] 
    return _to_range(l, start = l[0], stop = l[0], idx = 0, result = []) 

l = [1, 2, 3, 7, 8, 9, 11, 12, 15] 
result = get_range(l) 
print(result) 
>>> [(1, 3), (7, 9), (11, 12), (15, 15)] 
# I think it's better to fetch the data as it is and if needed, change it 
# with 
print(','.join('-'.join([str(start), str(stop)]) for start, stop in result)) 
>>> 1-3,7-9,11-12,15-15 

除非你完全不关心数据，那么在哪里只是追加STR（开始）+“ - ” + STR在_to_range功能（STOP）所以后来就没有必要额外的类型' - '。加入方法。

Answer 3

我将专注于您的主要问题的表现。我会给出2个解决方案：

1）如果存储的整数边界在A和B之间，并且可以创建一个布尔数组（即使可以选择一个位数组来扩展derange也可以存储）与（B - A + 2）元素，例如A = 0和B = 1 000 000，我们可以这样做（我会用C＃编写它，对不起XD）。此运行在O（A - B），是一个很好的解决方案，如果A - B小于号码的数目：

public string getIntRangesFromList(int[] numbers) 
    { 
     //You can change this 2 constants 
     const int A = 0;  
     const int B = 1000000; 

     //Create an array with all its values in false by default 
     //Last value always will be in false in propourse, as you can see it storage 1 value more than needed for 2nd cycle 
     bool[] apparitions = new bool[B - A + 2]; 
     int minNumber = B + 1; 
     int maxNumber = A - 1; 
     int pos; 
     for (int i = 0; i < numbers.Length; i++) 
     { 
      pos = numbers[i] - A; 
      apparitions[pos] = true; 

      if (minNumber > pos) 
      { 
       minNumber = pos; 
      } 
      if (maxNumber < pos) 
      { 
       maxNumber = pos; 
      } 
     } 

     //I will mantain the concatenation simple, but you can make it faster to improve performance 
     string result = ""; 
     bool isInRange = false; 
     bool isFirstRange = true; 
     int firstPosOfRange = 0; //Irrelevant what is its initial value 
     for (int i = minNumber; i <= maxNumber + 1; i++) 
     { 
      if (!isInRange) 
      { 
       if (apparitions[i]) 
       { 
        if (!isFirstRange) 
        { 
         result += ","; 
        } 
        else 
        { 
         isFirstRange = false; 
        } 

        result += (i + A); 
        isInRange = true; 
        firstPosOfRange = i; 
       } 
      } 
      else 
      { 
       if (!apparitions[i]) 
       { 
        if (i > firstPosOfRange + 1) 
        { 
         result += "-" + (i + A - 1); 
        } 
        isInRange = false; 
       } 
      } 
     } 

     return result; 
    } 

2）O（N *日志N）

public string getIntRangesFromList2(int[] numbers) 
    { 
     string result = ""; 

     if (numbers.Length > 0) 
     { 
      numbers.OrderBy(x => x); //sorting and making the algorithm complexity O(N * log N) 
      result += numbers[0]; 
      int countNumbersInRange = 1; 
      for (int i = 1; i < numbers.Length; i++) 
      { 
       if (numbers[i] != numbers[i - 1] + 1) 
       { 
        if (countNumbersInRange > 1) 
        { 
         result += "-" + numbers[i - 1]; 
        } 

        result += "," + numbers[i]; 
        countNumbersInRange = 1; 
       } 
       else 
       { 
        countNumbersInRange++; 
       } 
      } 
     } 

     return result; 
    } 

Answer 4

的最快的一个我可以想出，测试比我的机器上的解决方案快大约10％（按timeit）：

def _ranges(l): 
    if l: 
    l.sort() 
    return ''.join([(str(l[i]) + ('-' if l[i] + 1 == l[i + 1] else ',')) 
        for i in range(0, len(l) - 1) if l[i - 1] + 2 != l[i + 1]] + 
        [str(l[-1])]) 
    else: return '' 

上面的代码假定在列表中的值是唯一的。如果他们不这样做，很容易修复，但有一个微妙的黑客将不再工作，最终结果会稍微慢一点。

因为排序，我实际上定时了_ranges(u[:]); u是从包含235个子序列的范围（1000）中随机选择的600个整数; 83是单身人士，152人至少包含两个数字。如果列表被排序，则会节省很多时间。