整數列表到範圍

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人至少包含兩個數字。如果列表被排序，則會節省很多時間。