3

プロセスから取得されたトレースからのメソッドのリストがあります。基本的にループで呼び出されているものがあるかどうかを検出したいと思います。たとえば、私は持っているかもしれません

method1
    method2
    method2
    method2

「可能なループでmethod1によって3回呼び出されたmethod2」を表示する場合があります。

method3
    method1
    methodd
    methoda
    methodb
    methodc
    methodd
    methoda
    methodb
    methodc
    methodd

'methoda、methodb、methodc、methodedを可能なループで2回表示します'。

明らかに、ループがあるという保証はありませんが、少なくとも繰り返しパターンがあることはわかっています。唯一の入力は子のリストです（たとえば、上記のmethod2、method2、method2から）。

4

2 に答える 2

1

順序に従って子のリストを連結リストに挿入し、連結リスト ループ検出アルゴリズムを実行できます。

たとえば、一度にノードを移動する 1 つのポインターと、一度に 2 つのノードを移動する別のポインターの 2 つのポインターがあります。ループが存在する場合、高速のポインターは最終的に低速のポインターと同じノードになります。

于 2013-01-08T04:28:13.387 に答える
1

最長の一般的なプレフィックスとともにサフィックス配列を構築し、値 > しきい値 (K は別のしきい値) を持つ K 個の連続した LCP を見つけます。

検索では、見つかったサフィックスの候補 LCP がソース文字列内で連続している/重複していないことが必要です。検索アルゴリズム:

let minimum_iterations = 1
let minimum_pattern_length = 2
let src = source string
let suffix = sorted suffix array, 
             where each entry is suffix i0 (inclusive) to |src| (exclusive)
let lcp = longest common prefixes, 
             where lcp(i) = longest common prefix of suffix(i) and suffix(i-1) when i > 0,
             or 0 if i = 0

for i = 0 to |suffix|:
    if lcp[i] < minimum_pattern_length: continue        
    let j = i
    let iterations = 0
    let last_matched_i0 = suffix[i-1].i0
    while j < |suffix| and lcp[j] >= lcp[i]:
        if (suffix[j].i0 + lcp[i] + 1) = last_matched_i0: 
            iterations++
            last_matched_i0 = suffix[j].i0
        j++

    print 'pattern = ' .. suffix[i][0..lcp[i]] .. ' iterations = ' .. iterations
    print 'starting at ' .. suffix[j-1].i0 .. ' to ' .. suffix[i-1].i0 + lcp[i]

    skip pattern if wanted

(suffix[j].i0 + lcp[i] + 1) = last_matched_i0 一致したパターンが連続していることを確認してください。ソートされたサフィックス配列では常に前に来るため、両方のパターンである場合suffix[j]はインクルードすると想定しますsuffix[j-1]ababab

例: 3ababab65

サフィックス

  • 3ababab65
  • ababab65
  • ババブ65
  • abab65
  • bab65
  • ab65
  • b65
  • 65
  • 5

最長共通プレフィックス (LCP - サフィックス) と共に並べ替えられたサフィックス: LCP(i) は、SUFFIX(i) と SUFFIX(i-1) の間の最長の共通プレフィックスです。

  • 0 - 5
  • 0 - 65
  • 0 - 3ababab65
  • 0 - ab65
  • 2 - ab ab65
  • 4 -アバブab65
  • 0 - b65
  • 1 - b ab65
  • 3 -バブab65

LCP 候補者:

  • ab 65、ab ab65、ab abab65 - 連続、重複なし
  • abab 65、abab ab65 - オーバーラップ
  • b 65、b ab65 - 連続していない
  • bab 65、bab ab65 - オーバーラップ

考えられるパターン:

  • ab

次のケースを処理するには、コードを少し変更する必要があります。

アババ

aba と ababa のサフィックスがあり、LCP は 3 です。

または、これを行うこともできます...最短の繰り返しサブストリング...どれだけ効率的かはわかりません...しかし、はるかに簡単です。

于 2013-01-10T15:54:57.780 に答える