- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
import java.util.ArrayList;
public class Chapter19 {
/* find repeat chars in text (in all words of text)
* print repeat chars
*
*/
private String stringArray[] = { "Allocates ae neaw Setringa tehat",
"represeants tahe same saequence " };
final private String alfabetArray = "abcdefghijklmnopqrstuvwxyz";
private ArrayList <Character> repeatChars;
public void run() {
printStringArray();
repeatChars = new ArrayList<Character>();
extractRepeatChars();
if (!repeatChars.isEmpty()) {
printRepeatChars();
} else {
System.out.println("not repeat ");
}
}
private void printRepeatChars(){
System.out.println("");
for (char c : repeatChars) {
System.out.println(c);
}
}
private void printStringArray(){
System.out.println(" ");
for (String s : stringArray) {
System.out.println(s);
}
}
public String [][] parseStringArray() {
String wordsArray[][] = new String[stringArray.length][];
for (int i = 0; i < wordsArray.length; i++) {
wordsArray[i] = stringArray[i].split("\n|\t| ");
}
return wordsArray;
}
public int findRepeatCharInWordsArray(String [][]wordsArray, char c) {
for (int i = 0; i < wordsArray.length; i++) {
for (int j = 0; j < wordsArray[i].length; j++) {
if (wordsArray[i][j].indexOf(c) < 0) {
return 0; // zodyje c nerastas
}
}
}
return 1;
}
public void extractRepeatChars() {
String wordsArray[][] = parseStringArray();
for (char c : alfabetArray.toCharArray()) {
if (findRepeatCharInWordsArray(wordsArray, c) > 0) {
repeatChars.add(c);
}
}
}
} // end
Follow us!
Оценить структурность кода и где что подправить можна.
вот вам для сравнения мой говнокод.
C#
> return 0
> return 1
Тяжелое сишное наследие? :) В java есть boolean.
Задачу не совсем понял. Если я правильно понимаю код - он выводит буквы, которые есть во всех словах (если хоть в одном слове буквы нет - она не выводится). Так и надо?
foldl1 Set.intersection - тупо O(N), т.к. букв всего 26, и каждый интерсект считаем как O(1).
Set.toList тоже будет O(1), т.к. от количества слов не зависит.
Ну и в итоге, если я нигде не затупил, будет O(N * M * log(M)).
Ну или битмаски, как вариант. or по буквам, and по словам.
Ну разве что хранить в нем не булы и не количества, а индексы предыдущих букв, чтобы получился связный список. Тогда сброс будет не дольше чем количество разных букв в слове. И мы выходим на линейную асимптотику.
И мы можем получить ситуацию, когда у нас есть 1000 слов по 1000 букв и одно слово из 3 букв, но оно самое последнее?
Ну, видимо, имеется в виду 1000 одинаковых слов, состоящих из 1000 разных букв, чтобы получился наихудший случай?
На построение множеств сортировка не повлияет. На вывод результата - тоже. Остается оценить влияние на интерсекты.
Интерсекты в хаскелевском set'е выполняются за O(m+n), где m и n мощности исходных множеств. Пусть m - мощность аккумулятора, n - число разных букв в текущем слове. На n мы повлиять не можем, т.к. от сортировки слова просто меняются местами. m упадет с 1000 до 3. Т.к. в худшем случае без сортировки m и n были равны, а в лучшем (после сортировки) упали в район нуля, получим ускорение интерсектов где-то в 2 раза. Причем это ускорение в константе, а не в асимптотике: с ростом количества и длины слов оно так и останется в 2 раза.
Итого: выигрыш от сортировки составит <= 0.5 * T(intersection).
P.S. И я совсем не уверен, хотя и могу ошибаться, что сама сортировка не сожрет весь этот профит ;)
Онлайн это потоковая.
Сложность сортировки у нас зависит от количества слов как N*log(N), а интерсекты - линейно.
Поэтому сделаем такой вывод: при малом количестве слов сортировка может ускорить алгоритм не более чем на 0.5 * T(intersection). При большом количестве слов сортировка увеличит время работы.
Если уж рассматривать реальный случай - то он почти всегда будет пустым, поэтому if (commonChars.isEmpty()) break ускорит алгоритм еще больше :)
Это вопрос про реализацию, не про алгоритм. Чтобы отвечать на вопросы о сравнении асимптотики недостаточно, надо еще и константы конкретных реализаций оценивать :)
Ну вот что точно скажу - при большом объеме текста сортировка это однозначный фейл. Алгоритм со множествами сам-по себе потоковый, ему памяти надо на текущее множество, на множество-аккумулятор, ну и на I/O буферы. Причем мощность множеств ограничена мощностью алфавита. Если я там с ленивостью нигде не накосячил - хаскелевый код так и будет работать на потоке (а если не будет, то можно попрофайлить и распихать seq, чтобы работал). Алгоритм с сортировкой на потоке работать тупо не сможет.
В конце слова: common &= mask;
Этот способ по идее самый быстрый и в асимптотике, и на практике ;) Но с вполне понятными ограничениями.
Как-то так? http://ideone.com/uat5H5
http://rosetta-govnokod.ru
Не открывается ;( Пойти зарегать что-ли.
^\S*(\S)\S*(\s+\S*\1\S*)*\s*$
Нужная буква в первой группе
Кстати, возможно ли найти все буквы при условии, что длина слова не ограничена?
Или, если она ограничена, но длина регекспа не растёт экспоненциально с количеством букв?
так что ли?
\S*(\S)\S*
Или без повторений?
Пример приведите, я что то не понял Вас
А я хочу найти все общие буквы, т.е. о, е, з, д.
Если поставить условие "длина самого короткого слова - 1 буква", Ваша регулярка находит все общие буквы.
Если поставить условие с 2 буквами, найдётся строка вида "по полю опали", для которой найдётся только одна буква, а хочется две.
Можно написать что-то вида /^\s*\S*(\S)\S*(\S)\S*(?:\s+\S*\1\S*\2\S* |\s+\S*\2\S*\1\S*)*\s*$|^\s*\S*(\S)\S*(? :\s+\S*\1\S*)*\s*$/, чтобы иметь 2 буквы.
В общем случае это будет вида /F(N)|F(N-1)|...|F(1)/, где F(N) = ^\S*, N раз (\S)\S*, (?:\s+G(1)|G(2)|G(3)|...|G(N!)), где G(номер перестановки) = \S*\i1\S*\i2\S*...\iN\S*, а i1...iN - номера 1..N для текущего номера перестановки. Длина этой штуки растёт экспоненциально с ростом регулярного выражения.
Интересно, можно ли написать "по уму" и избавиться от экспоненты, а также - для бесконечного N.
можно найти самое короткое слово, растащить его по буквам, а потом собирать регулярку ^\s*\S*(simbol)\S*(\s+\S*simbol\S*)*\s*$ .
В подавляющем большенстве случаев либо самое маленькое слово будет однобуквенным, или выборка не будет превышать 10.
А с участием другого кода (наши возможности тут непомерно возрастают) можно ещё умерить жадность первой \S*: /^\s*\S*?(\S)\S*(\s+\S*\S\S*)*\s*$/ и, "откусывая" первый символ строки до того, как наступит пробел после первого слова, применять регулярку к каждой подстроке.
^(\S)\S*(\s+\S*\1\S*)*\s*$
и применять к обрезаемой строке пока 1 символ не станет пробельным
на счет новых веяний - ничего не знаю, я на шарпе прогаю, там старые добрые PCRE без сахара
C#
Схема отработаная годами
А вообще нужно должное отдать, что человек пытается сдать свою лабу
Тута мельком прочитал посты борманда, да задание вы поняли правильно. Моя идея заключалась в чем - если есть символ из множества в каждом слове хоть один раз - мы его выводим, ну или в коллекцию пишем. Если он повторяется в том же слове, банально не выводим его.
Такие задачи тренируют мышление и способствуют набивке руки. Задания брал из Книжки "Ява промышленное программирование".
А ошибки были не на уровне java а на уровне проэктирования. От того, что ты сменишь язык голова по другому работать не начнет.
Набросал в консоли ipython минут за 5-10.
import string
text = "The interpreter prients the result oef streing operations"
def find(text):
words = text.split()
repeat_chars = []
for j in string.letters:
for i in words:
key = 1
if not j in i:
key = 0
break
if key == 1:
repeat_chars.append(j)
return repeat_chars
print find(text)
А т.к. мощность алфавита константна, считаем что алгоритм имеет сложность O(n).
Подумал о том, что для машины N * M и M * N могуть быть совершенно разными вещами: много раз смотреть содержимое небольшого датасета должно быть гораздо выгодее, чем несколько раз просматривать содержимое большого датасета...
> много раз смотреть содержимое небольшого датасета должно быть гораздо выгодее
Чисто из-за работы с внешними устройствами, такими как память. Если бы у проца была одинаковая скорость доступа к любому месту датасета, порядок не имел бы никакого значения :)
На мой взгляд исключать старые варианты лучше чем добалять новые. Берем среднее слово и вычеркиваем буковки
А вообще задача бесполезная в такой постановке.
P.S. Код с пересечением множеств это и есть то самое вычеркивание.
> И потерять поточность алгоритма.
Выше где-то уже wvxvw предлагал сортировать слова по длине... Там я доказал (в меру своих математических способностей), что это даст прирост максимум вдвое (без учета потерь на сортировку!).
Вот и тут, походу, будет та же самая ситуация.
> Разность множеств.
Можно уточнить, каких?
Например у нас срока в которой первые 100 слов состоят из 1000 букв, а потом идут слова по 5 букв. Нам проще пропустить длинные слова и начать проверять с 1001ого, а потом вернуться и проверить первые. проверять придется не 1000 на 1000 а 5 на 1000. тем более есть шанс, что их вообще проверят не придется (пересечение опустеет)
Вот только на это и надежда :)
> Нам проще пропустить длинные слова
Ну на потоковость алгоритма я так понимаю вам наплевать? :) Эти 100 слов же где-то придется хранить, пока до них дойдет очередь. А если они там все такие... Вот тут-то в игру вступят скорости внешних носителей, и вся ваша оптимизация превратится в тыкву ;)
P.S. А если слова и так читаются с диска - то, имхо, всем насрать на порядок слов, т.к. множества будут строиться и пересекаться гораааздо быстрее, чем слова будут подкачиваться с диска...
- "Продавец, заверните мне, пожалуйста, пару сокетов в кольцо".
Хорошо, если эти слова поместились в память, и уже там лежат. А если они, к примеру на диске, или еще хуже вытекают из сокета? Тоже предлагаете 2 раза парсить начальный фрагмент файла? :)
> Например у нас срока в которой первые 100 слов состоят из 1000 букв, а потом идут слова по 5 букв.
А это типичный худший случай. Вон quicksort тоже в худшем случае сливается как говно, затрачивая O(n^2) времени. Но все же прекрасно знают, что худший случай он редкий, и юзают квиксорт.
P.S. Опишите свой алгоритм в каком-нибудь виде (код, псевдокод), чтобы было что обсуждать. Иначе я вот не понимаю, какие множества вы откуда собираетесь вычитать.
во у нас есть массив слов. не все ли равно какое из них брать? ну так будет брать из не с первого, а с N.
А для пропущенных слов проверки будет дешевле.
И если уж мы режем строку на слова то можно стразу найти кратчайшее, да от него и плясать.
"шла саша по шоссе и сосала сушки"
с "и" выгодней начать
Я не предлагаю кардинально новый алгоритм, я предлагаю немного усовершенствовать старый.
Сорри за невнятные объяснения - засыпаю
Ок, понял в чем соль.
Ну вот смотрите, попробую попроще объяснить. Алгоритм состоит из двух подзадач - построения множеств и их пересечения. На построение ваша оптимизация никак не влияет. Пересечения ускорятся.
Но построения занимали бОльшую часть времени O(n*log(n)) против O(m+k) у деревянных сетов или даже O(k) для хешсетов... Поэтому эта оптимизация физически не может дать профита более 50%...
Стоит ли ради ускорения не более чем в 2 раза (а скорее всего меньше) терять поточность алгоритма, каждый пусть решает для себя :)
P.S. Если интересно - попробуйте запилить и побенчить исходный и модифицированный алгоритм на примере, который приводили выше (100 слов по 1000, и потом одно короткое), и на средненьком, где слова более-менее разбросаны. Я более чем уверен, что в обоих случаях ускорения более чем в 2 раза не получится. Если получится - снимаю шляпу ;)
P.P.S. Огромное ускорение может получиться только из-за break'а, но давайте все-таки предполагать, что ответ почти всегда не пуст. Иначе кому интересна такая задача, где всегда пустой ответ?
Ну да) Вообще если пологаться на break нужно распараллелить поиск пересечений
Больше чем в 2 раза при наличии общих буковок таки не получится - наоборот замедлится. Увы и ах я полагаюсь на реальные ситуации)
Тут возникает другой вопрос - нафига? У этого алгоритма нет ценности)
P.S. Все сообщения сливаються в один столбец - говнокод такой говнокод
P.S.S. Сегодня по радио задачку передавали для среднего человека
"в доме 7 этажей. на первом живут 2 на втором 4 на третьем 6 и т.д (пирамида перевернутая)
на каком этаже лифт вызывается чаще?"
Ответ всем понятен. А теперь попытайтесь обьяснить без помощи математики)
Но он не сказал, люди ли живут в доме и есть ли там вообще лифт...
Лифта нет, но он вызывается? :)
А вдруг у них 3 этажа под землей, и поэтому лифт чаще всего вызывается на третий?
Если лифта нет, то на всех этажах он вызывается одинаково редко...
И, при этом, потеряли потоковость алгоритма. Что имхо очень плохой размен.
На сишке можно написать эффективную реализацию, используя лишь 3 дополнительных массива размера W (проблема только в том, что оно заранее не известо :): ).
Если алфавит совсем мелкий (например кириллица или латиница), имхо, лучше всего битмаски поюзать.
Еще один потоковый алгоритм выше приводил epic_fail. Там нужно два массива по размеру алфавита. Его алгоритм дает строгое O(n) независимо от размера алфавита (ну еще O(m) на выводе), но вот константа вырастет когда массивы не влезут в кеш.
Производительность будет хуже множеств только на больших алфавитах и коротком тексте.
Ну ок, этот способ эффективен для небольших алфавитов (в районе 1000000 символов). Так устроит? :)
В теории, на бальших данных - другое дело, юзать другие алгоритмы.
http://govnokod.ru/13661#comment192861 ?
А в яваскрипте даже с ним не осилили ;)
Вылетит с исключением, если seq будет пустым.
из книжек по питону - старайтесь меньше использовать циклы, а больше вшитые функции. так что ваш предыдуший код ок.
http://ideone.com/3lG30S
A &= В <==>A = A &B
обычно это побитовое И
Только неувлекайтесь сильно.