Mam długi ciąg i listę [end-index, string] jak następujące:

long_sentence = "This is a long long long long sentence"
indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]

Element 6, "is" wskazuje, że 6 jest indeksem końcowym słowem "is" w ciągu. W końcu chcę uzyskać następujący ciąg:

>> print long_sentence
This .... long ......... long sentence"

Próbowałem takiego podejścia:

temp = long_sentence
for i in indices:
    temp = temp[:int(i[0]) - len(i[1])] + '.'*(len(i[1])+1) + temp[i[0]+1:]

Chociaż wydaje się, że działa, podejmuje wyjątkowo długi czas (ponad 6 godzin na 5000 strun w pliku 300 MB). Czy istnieje sposób na przyspieszenie?

2
Legend 15 listopad 2011, 11:37

4 odpowiedzi

Najlepsza odpowiedź

Za każdym razem, gdy robisz to temp = temp... przypisanie, Python musi utworzyć nowy ciąg (ponieważ struny Pythona są niezmienne).

To, co możesz zrobić zamiast tego obrócić ciąg do listy znaków, a następnie działaj na liście znaków, a następnie ponownie dołącz do tej listy z powrotem do łańcucha ponownie.

long_list = list(long_sentence)
for end, repstr in indices:
    long_list[end-len(repstr):end] = ['.'] * len(repstr)
new_sentence = ''.join(long_list)
3
Amber 15 listopad 2011, 07:47

Zwykle koncentruje się na napisaniu najczystszego, czytelnego zwięzłego kodu pierwszy i optymalizuj drugi; I to dokładnie podejście, które zrobiłeś, Bravo! 6 godzin wydają się nieorwalni i czas na optymalizację. Wyraźnie rozdzieliłeś czas, aby utworzyć ciąg wymiany od czasu, aby wygenerować listę indeksów w pierwszej kolejności?

benchmarking pokazuje Wymienia listy , dołącza i fałszywe pliki są najszybsze dla kontatenacji łańcuchowych. To był dość stary artykuł - możesz samodzielnie uruchomić benchmarku, aby potwierdzić wyniki - chociaż prawdopodobnie nadal się trzyma.

3
Will 15 listopad 2011, 07:44

Możesz uniknąć zachowań o (n) za pomocą zestawów do testowania członkostwa i str.join , aby połączyć wyniki:

>>> redacts = set()
>>> indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]
>>> for end, substr in indices:
        redacts.update(range(end-len(substr)+1, end+1))
>>> ''.join([('.' if i in redacts else c) for i, c in enumerate(long_sentence)])
'This .... long .... .... long sentence'

Alternatywnie możesz użyć Bytearray , który pozwala mu zmienić "ciąg" w miejscu:

>>> arr = bytearray(long_sentence)
>>> for end, substr in indices:
        arr[end-len(substr)+1: end+1] = '.' * len(substr)
>>> str(arr)
'This .... long .... .... long sentence'

Ta ostatnia technika działa tylko dla ciągów nie-Unicode.

3
Raymond Hettinger 15 listopad 2011, 07:58

Możesz wykonać zastąpienie znaków za pomocą Mutable Mutable array Typ:

>>> import array

>>> long_sentence = "This is a long long long long sentence"
>>> indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]

>>> temp = array.array('c', long_sentence)  # Could replace long_sentence too
>>> for end, substr in indices:
...     temp[end-len(substr)+1:end+1] = array.array('c', '.'*len(substr))
...     
>>> temp
array('c', 'This .... long .... .... long sentence')

Nowy ciąg może być zapisany do pliku wyjściowego z:

temp.tofile(your_file)

(Sam ciąg jest zwracany przez temp.tostring().)

Takie podejście ma tę zaletę , zapobiegając zbyt wielu nowych strunowi od stworzenia przez krojenie , co wymaga czasu. Kolejną zaletą jest to, że jest to wydajna pamięć : Aktualizacja ciągów jest wykonywana na miejscu (jest wyświetlana przez adres znajdujący się w temp.buffer_info(), który pozostaje stałą). Efektem ubocznym jest to, że ta wydajność pamięci może zezwolić na komputer Unikać wymiany , a tym samym prędkość jeszcze bardziej.

Możesz także przyspieszyć rzeczy przez buforowanie '.'*len(substr) '.'*len(substr) przez specjalną klasę DotString metodą niestandardową __getitem__, gdzie DotString[4] zwraca DotString[4] X4}} itd.

PS : Większość prób optymalizacji korzysta z profilowanie pierwszej. Możesz profilować swój program za pomocą:

python -m cProfile -o stats.prof <Python program name and arguments>

Następnie możesz przeanalizować czasy:

python -m pstats stats.prof

Pierwsze polecenie, które zwykle biegniesz, to sort time (sortowanie funkcji według czasu spędzonego ściśle wewnątrz kodu funkcyjnego), a następnie stats 10 (pierwsze 10 najdłuższych funkcji wykonania).

Zrobiłbyś to w skróconej wersji pliku wejściowego, aby czas biegu nie był zbyt długi. Powiedzie to, które funkcje biorą najwięcej czasu i powinno być przedmiotem optymalizacji.

pps : typ 'c' używany w powyższym przykładzie jest przeznaczony dla ciągów bajtów (typowo kodowanie ASCII). Sznurki znaków (stroje Unicode AKA) można obsługiwać za pomocą 'u'.

3
Eric O Lebigot 15 listopad 2011, 21:33