查找包含分隔值的數組的最長切片

我有一個很長的一維正整數數組。從一端開始，我需要找到數組中最長的片/塊，其值至少與該片的所有組成部分相距一個數字。查找包含分隔值的數組的最長切片

即，我想對數組進行分區（從左邊開始），使得每個分區包含的元素與該分區中的所有其他元素相距不止一個單元。

例如：

[1,1,9,5,3,8,7,4,1,2] - > [1]，[1,9,5,3]，[ 8]，[7,4,1]，[2]
[1,5,9,1,3,6,4,2,7,0] - > [1,5,9]，[1 ，3,6,4]，[2,7,0]

Bellow，我在Fortran中編寫了一些代碼，可以讓我找到第一個這樣的重複先前值的點。

掩模是LOGICAL陣列
陣列是有問題的陣列
n是陣列

我可以很容易地擴展，以找到完整的分區的長度。

mask = .FALSE. 

DO i = 1,n 

    k = array(i) 

    IF (mask(k)) THEN 
     PRINT*, i 
     EXIT 
    ELSE 
     mask(k-1 : k+1) = .TRUE. 
    END IF 

END DO

所以我的問題是，有沒有更好的方法（算法）做到這一點？當我說得更好時，我的意思是速度。我不介意記憶成本。

來源

2017-05-08 physkets

@ d_1999哦，我想要的是一個分區，使得每個分區只有數量超過該分區的任何其他組成部分的數量。 – physkets

如果您不需要流式解決方案，那麼可以計算第二個增量數組，然後在增量數組中的零點處打破（輸出）數組。使用-O3或一些編譯指示！DIR可以輕鬆獲得delta的矢量化代碼？ SIMD或！？OMP SIMD（OpenMP）很容易。然後掩模仍然可以用來顯示零點在哪裏。它取決於一個非常長的數組有多大（？），但是你說內存不是問題......你應該能夠在矢量化增量部分獲得帶寬限制。掩碼也可以是一個整數以跟蹤數組子區 – Holmz

只是一些想法：在第一個示例中，您允許'9'和'8'出現在同一個片段中嗎？它應該不是'[1]，[1,9,3]，[8]，[7,4,1]，[2]'？此外，這遵循你從左邊*的規則。在[1,1,9,3,8,10,5,1]的情況下，你想要[1]，[1,9,3]，[8,10,5,1]'（左）還是你想要拾取較長的最大片[1]，[1,9]，[3,8,10,5,1]'。 – Steve

概念上，它可能是這個樣子......

DO i = 1,n-1 
    Delta(I) = array(I+1) - array(I) 
ENDDO 

iMask = 0 
WHERE(ABS(Delta) < 2) iMask =1 
ALLOCATE(splits(SUM(iMask))) 

K=0 
DO I = 1, n-1 
    IF(iMask(I) == 0) CYCLE 
    K = K +1 
    Splits(K) = I 
ENDDO 

!... DEALLOCATE(Splits)

然後，只需打印出拆分值之間的數據，這可能是由數熄滅，你可能還需要做些什麼的第N點，所以它取決於您的實施，以及您的增量是「太下一個點」還是「從最後一個點」。

在這種情況下，我用imask作爲整數而不是邏輯，所以我可以使用SUM。

來源

2017-05-09 11:07:33 Holmz

我的確在想這件事，但我必須在所有'轉變'中找到增量。你們正在換一個單位。這隻會給我最近的鄰居碰撞。這將給予'第一'分區。我不知道這一切是否會使它變得更好或更糟。我想我必須執行並檢查。 – physkets

您仍然可以擁有LOGICAL數組並使用COUNT與SUM執行相同的工作。 – physkets

感謝英特爾網站上的@physkets總結它墨黑提到「互聯網，真實還是複雜」，我沒有看到位級別。如果我已經考慮過了，我可以使用Union/map，但是對於我正在處理的項目，無論如何我都需要整數。 – Holmz

我最初的反應是天真的方法：

保存指數範圍在你目前正在擴大分區（partitionNumber從iStart到iEnd）
採取的下一個點與指數iEnd+1和循環從iStartiEnd測試候選點不在當前成員的1範圍內
如果候選人未通過包含測試，請在其自己的分區中重新啓動iStart和i增加partitionNumber
增量iEnd。

如果您希望分區大部分時間很短，那麼這應該很快。如果您預計長整數增加或減少的鏈可以保存分區中值的min和max包括快速測試以查看您的候選人是否超出範圍。

我沒有測試過這個，我的fortran可能有點生疏，但我認爲它代表了上面的算法。

partitionNumber = 1 
iStart = 1 
iEnd = 1 
iCandidate = iEnd + 1 
arrayMember(iStart) = partitionNumber 
DO WHILE (iCandidate <= N) 
    DO j = iStart,iEnd 
     IF (ABS(array(iCandidate)-array(j)) < 2) 
      partitionNumber = partitionNumber + 1 
      iStart = iCandidate 
      EXIT 
     END IF 
    END DO 
    arrayMember(iCandidate) = partitionNumber 
    iEnd = iEnd + 1 
    iCandidate = iEnd + 1 
END DO

你的兩個例子操作，我希望它與條目

[1,1,9,5,3,8,7,4,1,2] -> [1,2,2,2,2,3,4,4,4,5]（代表[1],[1,9,5,3],[8],[7,4,1],[2]）
[1,5,9,1,3,6,4,2,7,0] -> [1,1,1,2,2,2,3,3,3,3]（代表[1,5,9],[1,3,6],[4,2,7,0]）

我回到arrayMember不完全確定我明白你如何將你的版本擴展到所有分區，但是這個mi ght保存在定義mask的大小MAX(array)？

來源

2017-05-10 10:58:50 Steve

我猜這將比我發佈的示例代碼更長。就我而言，我不必每次都計算差異。否則，它看起來是一樣的。那不是嗎？ – physkets

@physkets我認爲這種方法是不同的：你的代碼用來檢查一個slice，並且爲每個slice定義一個bools掩碼，長度爲MAX（array）來阻塞整數，你必須移動，將'.TRUE.'分配給值，然後在開始檢查下一個分區時重置。無法評論哪種方法會更快，但我認爲這些方法足夠不同以至於兩者都可以測試（如果我的代碼實際上只進行最小的更改編譯！） – Steve

@physkets您可能是對的。正如我所說，這是我最初的想法，而且我的代碼使用'mask（array（i））'我有點困惑，我現在可以 – Steve

查找包含分隔值的數組的最長切片

回答

相關問題