Temat: Upload na FTP, oraz synonimy w tekście
Ale czego ja mam dowodzić? :)
Regex wyszykuje wszystkie literały między podanymi separatorami. Zakładam, że działa poprawnie :) Znalezione literały to listy synonimów. Pętla przechodzi po znalezionych listach i dzieli je względem podanego separatora na synonimy. Funkcja dzieląca również jest wbudowana, więc zakładam, że działa poprawnie. Przed podziałem literał jest oczyszczany z wiodącego i końcowego separatora. j.w. W tekście źródłowym definicja synonimów (literał od { do }) zamieniamy jest na losowo wybrany z dostępnej aktualnie puli synonim. Funkcja Replace i Next - j.w. Jest to najzwyklejsze find/replace.
Trzeba do tego wyciągania zeszytu ze studiów, indukcji, szukania niezmienników i dowodu zbieżności (iteracje po skończonych listach elementów) ? :)
----------
A tymczasem... :)
Ale to już nie jest interesujące. Ot - kombinowanie w pętli, jak na laborkach. W dodatku takie rozwiązanie jest bardziej podatne na błędy. To z Regexem ma jedną zaletę - przy niewielkiej ilości danych (gdy jeszcze jest dostatecznie szybkie) jest intuicyjne i proste, można dowolnie zmieniać separatory na wieloznakowe. To jest jeden z przykładów, gdy gorsze obliczeniowo rozwiązanie jest lepsze z innych względów - mniejsza podatność na błędy, czytelność, łatwość modyfikacji.
PS: jeszcze dla miliona kolekcji - 6.4 sek.
To rozwiązanie ma jednak wadę - jest nieodporne na niewłaściwy format danych. A dodawanie kolejnych warunków bardzo zaciemni obraz, więc - z czystego lenistwa, zakładam, że tekst ma właściwy format, tzn. że delimitery definicji są sparowane.
-----------------------
EDIT: Oto kod. Założenie - ŻADNYCH "replace", żadnych "IndexOf", jedynie
dopisywanie na końcu stringu i to za pomocą StringBuildera. Gdyby ktoś miał pomysł, jak to ładniej zapisać...
private static string ReplaceWithSynonyms(string sourceText)
{
Random rnd = new Random();
// synonimy dostępne w obrębie bieżącej definicji
List<string> synonyms = new List<string>();
bool readSynonym = false;
string synonym=string.Empty;
// Tak, wiem, że można wziąć synonyms.Count, ale - żadnych
// dodatkowych pętli :]
int synonymsCount = 0;
StringBuilder newText = new StringBuilder();
for (int i = 0; i < sourceText.Length; i++)
{
// jeśli delimiter początku definicji...
if (sourceText[i] == '{')
{
// siostro, mamy synonim.
synonymsCount++;
// W next iteracji będziemy
// traktować znaki z wejścia jak znaki słowa synonimu.
readSynonym = true;
continue;
}
if (sourceText[i] == '}')
{
// jeszcze cieplutki synonim do kolekcji dostępnych
// w zakresie tej definicji
synonyms.Add(synonym);
// Na razie koniec. Czyścimy, zamiatamy. Wyłączamy tryb
// "synonim detected". Od tej pory znaki z wejścia
// będziemy zwyczajnie przepisywać na wyjście.
synonym = string.Empty;
readSynonym = false;
// do dotychczasowego tekstu doklejamy jeden z synonimów
newText.Append(synonyms[rnd.Next(synonymsCount)]);
// taaak, to może być czasochłonne. Można to ominąć.
// Dodatkowe indeksy "lower bound" i "upper bound" dla
// funkcji rnd.Next(lower, upper) załatwią problem -
// nie trzeba czyścić listy, tylko do niej dopisywać.
synonyms.Clear();
// TAK, wiem, że w tej chwili synonyms.Count == 0 :]
synonymsCount = 0;
continue;
}
// Tryb czytania synonimu
if (readSynonym)
{
// bo beleczka mogła być składową tekstu
// TAK, wiem, nie zaimplementowałem tego dla { i } :]
if (sourceText[i] == '|')
{
// czytanie bieżącego synonimu - zakończone.
synonyms.Add(synonym);
synonym = string.Empty;
// a skoro była beleczka, to mamy next synonim
synonymsCount++;
continue;
}
// kolejne znaki są częścią słowa - synonimu.
synonym += sourceText[i];
continue;
}
// nie jesteśmy w trybie "synonim detected", więc przepisujemy
// znaki z wejścia na wyjście.
newText.Append(sourceText[i]);
}
return newText.ToString();
}
O(n). Jak się "rozkręciło", to nawet 5.6 sek. Niższego rzędu już nie będzie (jednokrotne przejście przez zbiór danych; Clear() -pętla- nie jest operacją dominującą), ale może ktoś jeszcze zmniejszy stałą.
Adrian Olszewski edytował(a) ten post dnia 10.09.11 o godzinie 00:22
пропозиції роботи
