4

この質問をコード レビュー エリアに移動してください。以下のコードがジャンクであることを知っており、重要なフィードバックがあれば完全に書き直したいので、そちらの方が適しています。私はほとんど車輪を再発明しています。

# Description: you are given a bitwise pattern and a string
# you need to find the number of times the pattern matches in the string.
# The pattern is determined by markov chain.
# For simplicity, suppose the ones and zeros as unbiased coin flipping
# that stops as it hits the pattern, below.
#
# Any one liner or simple pythonic solution?

import random

def matchIt(yourString, yourPattern):
        """find the number of times yourPattern occurs in yourString"""

        count = 0
        matchTimes = 0

        # How can you simplify the for-if structures?
        # THIS IS AN EXAMPLE HOW NOT TO DO IT, hence Code-Smell-label
        # please, read clarifications in [Update]

        for coin in yourString:
            #return to base
            if  count == len(pattern):
                    matchTimes = matchTimes + 1
                    count = 0

            #special case to return to 2, there could be more this type of conditions
            #so this type of if-conditionals are screaming for a havoc
            if count == 2 and pattern[count] == 1:
                    count = count - 1

            #the work horse
            #it could be simpler by breaking the intial string of lenght 'l'
            #to blocks of pattern-length, the number of them is 'l - len(pattern)-1'
            if coin == pattern[count]:
                    count=count+1

        average = len(yourString)/matchTimes

        return [average, matchTimes]



# Generates the list
myString =[]
for x in range(10000):
    myString= myString + [int(random.random()*2)]

pattern = [1,0,0]
result = matchIt(myString, pattern)

print("The sample had "+str(result[1])+" matches and its size was "+str(len(myString))+".\n" +
        "So it took "+str(result[0])+" steps in average.\n" +
        "RESULT: "+str([a for a in "FAILURE" if result[0] != 8]))


# Sample Output
# 
# The sample had 1656 matches and its size was 10000.
# So it took 6 steps in average.
# RESULT: ['F', 'A', 'I', 'L', 'U', 'R', 'E']

[アップデート]

ここで理論について少し説明します。おそらく、問題はそのように単純化できます。上記のコードは、A以下の遷移行列を使用してマルコフ連鎖を構築しようとしています。100コイントスとイメージできるパターンがそれにあたる。

>>> Q=numpy.matrix('0.5 0.5 0; 0 0.5 0.5; 0 0.5 0')     
>>> I=numpy.identity(3)
>>> I
array([[ 1.,  0.,  0.],
       [ 0.,  1.,  0.],
       [ 0.,  0.,  1.]])
>>> Q
matrix([[ 0.5,  0.5,  0. ],
        [ 0. ,  0.5,  0.5],
        [ 0. ,  0.5,  0. ]])
>>> A=numpy.matrix('0.5 0.5 0 0; 0 0.5 0.5 0; 0 0.5 0 0.5; 0 0 0 1')
>>> A
matrix([[ 0.5,  0.5,  0. ,  0. ],
        [ 0. ,  0.5,  0.5,  0. ],
        [ 0. ,  0.5,  0. ,  0.5],
        [ 0. ,  0. ,  0. ,  1. ]])

問題のは、上記average 8のマトリックスの最初の行の値の合計になります。N=(I-Q)^-1Q

>>> (I-Q)**-1
matrix([[ 2.,  4.,  2.],
        [ 0.,  4.,  2.],
        [ 0.,  2.,  2.]])
>>> numpy.sum(((I-Q)**-1)[0])
8.0

これで、この明らかにパターンマッチングのみの問題がマルコフ連鎖になることがわかるでしょう。乱雑な for-while-if 条件をマトリックスやマトリックスに似たものに置き換えることができない理由がわかりません。それらを実装する方法はわかりませんが、特に分解する必要がある状態が多い場合は、イテレータを使用して研究することができます。

しかし、Numpy で問題が発生しました。それは何のために、何の-InfためにあるNaNのでしょうか? (I-Q)**-1上記のマトリックスから収束する値を確認します。NからN=I+Q+Q^2+Q^3+...=\frac{I-Q^{n}}{I-Q}です。

>>> (I-Q**99)/(I-Q)
matrix([[  2.00000000e+00,   1.80853571e-09,             -Inf],
        [             NaN,   2.00000000e+00,   6.90799171e-10],
        [             NaN,   6.90799171e-10,   1.00000000e+00]])
>>> (I-Q**10)/(I-Q)
matrix([[ 1.99804688,  0.27929688,        -Inf],
        [        NaN,  1.82617188,  0.10742188],
        [        NaN,  0.10742188,  0.96679688]])
4

3 に答える 3

2 
def matchIt(yourString, yourPattern):
        """find the number of times yourPattern occurs in yourString"""

以下の使用は許可されていますか？

yourString.count(yourPattern)

あなたの場合myString、10000文字の実際の文字列として、patternまた文字列として作成し、単純なpythonicな方法で出現を数えることができます.

編集

patternin text(文字列またはリストのいずれか) の (重複する) 出現回数を示すワンライナーは、次のようになります。

nbOccurences = sum(1 for i in xrange(len(text)-len(pattern)) if text[i:i+len(pattern)] == pattern)
于 2011-01-12T18:12:25.133 に答える
1

わかりました - 標準的な (-ish) 文字列検索:

def matchIt(needle, haystack):
    """
    @param needle:   string, text to seek
    @param haystack: string, text to search in

    Return number of times needle is found in haystack,
        allowing overlapping instances.

    Example: matchIt('abab','ababababab') -> 4
    """
    lastSeenAt = -1
    timesSeen = 0
    while True:
        nextSeen = haystack.find(needle, lastSeenAt+1)
        if nextSeen==-1:
            return timesSeen
        else:
            lastSeenAt = nextSeen
            timesSeen += 1

しかし、あなたは数字のリストにこれをしたいですか? 問題ない; 次のように、find() メソッドを使用してリスト クラスを作成するだけです。

import itertools
class FindableList(list):
    def find(self, sub, start=None, end=None):
        """
        @param sub: list, pattern to look for in self

        @param start: int, first possible start-of-list
            If not specified, start at first item

        @param: end: int, last+1 possible start-of-list
            If not specified, end such that entire self is searched

        Returns;
            Starting offset if a match is found, else -1
        """
        if start is None or start < 0:
            start = 0

        # N.B. If end is allowed to be too high,
        # zip() will silently truncate the list comparison
        # and you will probably get extra spurious matches.
        lastEnd = len(self) - len(sub) + 1
        if end is None or end > lastEnd:
            end = lastEnd

        rng = xrange if xrange else range
        iz  = itertools.izip
        isl = itertools.islice

        for pos in rng(start, end):
            if all(a==b for a,b in iz(sub, isl(self, pos, end))):
                return pos

        # no match found
        return -1

次に、例は次のようになります

matchIt([1,2,1,2], FindableList([1,2,1,2,1,2,1,2,1,2])) -> 4

コードは次のようになります。

# Generate a list
randIn = lambda x: int(x*random.random())
myString =[randIn(2) for i in range(10000)]

pattern = [1,0,0]
result = matchIt(pattern, myString)

print("The sample had {0} matches and its size was {1}.\n".format(result, len(myString)))
于 2011-01-12T18:50:46.280 に答える
0

これは準備ができていません。

同様の質問ですが、ここでは主にグラフライブラリに焦点を当てており、同様の質問ですがC#では役立つかもしれません。

この質問に関連するファイルは./networkx/generators/degree_seq.py(997 行、指定された度数シーケンスでグラフを生成することについて) であり./networkx/algorithms/mixing.py (line 20, function degree_assortativity(G) about probability based graphs)、そのソース コードが 92 の参照を参照していることにも注意してください。車輪を再発明するかどうかはわかりません。convert.cigraph の場合は、加重エッジに関するファイルの 835 行をお読みください。Networkxのソースはこちらから、 igraph のソースはこちらから入手できます。前者は BSD ライセンスの下で Python で作成されているのに対し、igraph は GNU (GPL) の下で C で作成されていることに注意してください。

Networkx を使い始めるには、jUnits ファイルから加重グラフを作成するのに役立つ行がありますtest_convert_scipy.py。

def create_weighted(self, G): 
    g = cycle_graph(4)
    e = g.edges()
    source = [u for u,v in e]
    dest = [v for u,v in e]
    weight = [s+10 for s in source]
    ex = zip(source, dest, weight)
    G.add_weighted_edges_from(ex)
    return G

したがって、マルコフ連鎖を作成するには、ここで有向加重グラフについて助けてください。おそらく次のようなものです。

>>> DG=nx.DiGraph()
>>> DG.add_weighted_edges_from([(0,0,0.5),(1,1,0.5),(3,3,1),(0,1,0.5),(1,2,0.5),(2,3,0.5), (2,1,0.5)])

あるいは、他の確率過程の場合と同様に、すぐに使えるマルコフ連鎖生成ツールがあるかもしれません。詳細はこちら. あなたの例のように、例外的な値でグラフを分析したり、異なるセットで試行したりするアルゴリズムが見つかりません。おそらく何もないため、他の応答者のソリューションに固執する必要があります。

于 2011-01-13T18:03:01.563 に答える