LINUX.ORG.RU

Снова задачка

 , , ,


0

3

Теперь Седжвик.

Дано:

Напишите эффективную программу, которая определяет длину самой большой последовательности пробелов в данной строке, просматривая как можно меньшее количество символов.

Подсказка:

С возрастанием длины последовательности пробелов программа должна выполнятся быстрее.

Сам код подсчета пробелов может быть например таким:

#include <iostream>
#include <string>

int count( const std::string& input )
{
	int iSpaces = 0;

	for (int i = 0; i < input.size(); ++i)
		if (input[i] == ' ') ++iSpaces;

	return iSpaces;
}

int main()
{
	std::string input;
	
	std::cout << "Enter text: ";
	std::getline( std::cin, input );

	int numSpaces = count( input );

	std::cout << "Number of spaces: " << numSpaces << std::endl;
	std::cin.ignore();

	return 0;
}

То есть, интуиция мне подсказывает, что время выполнения искомой программы не менее чем O(N). Ну сосчитаем мы пробелы, дальше что? Загнать их в структуру данных X и отсортировать? Бред, по-моему...

★★★★★

Последнее исправление: Twissel (всего исправлений: 3)

Ответ на: комментарий от Deleted

Для начала, конечно же на Сишечке :)

Я, конечно, извиняюсь за теги, просто не проснулся...

Twissel ★★★★★
() автор топика
/**
 * Определяет длину самой большой последовательности пробелов 
 * в данной строке.
 *
 * @param str [in] -- строка с пробелами.
 * @return длина последовательности пробелов.
 */
unsigned long
count_max_spaces(char* str)
{
  unsigned long max_spaces = 0;
  
  for (unsigned long i = 0; i < strlen(str);)
    {
      unsigned long max_spaces_in_sequence = 0;

      while (' ' == str[i++])
	{
	  ++max_spaces_in_sequence;
	}

      if (max_spaces_in_sequence > max_spaces)
	{
	  max_spaces = max_spaces_in_sequence;
	}

      if (max_spaces > strlen(str) - i)
      	{
      	  /* 
	   Количество оставшихся символов меньше длины самой
      	   большой последовательности пробелов.
	   Т. е. большей последовательности гарантированно не будет.
	  */
      	  break;
      	}
    }

  return max_spaces;
}
Deleted
()

Идея алгоритма

Пробежаться по по строке с увеличивающимся шагом.
1) Взять шаг 1 символ. 2) Идти по последовательности пока текущий и предыдущий символ не будут пробелами. Проверить что это последовательность пробелов и запомниить ее длину. 3) Если длина L этой последовательности больше уже найденной, то увеличить размер шага прохода до L/2 (м.б. можно лучше подобрать коэффициент). 4) go to 2.

four_str_sam
()

С возрастанием длины последовательности пробелов программа должна выполнятся быстрее

Это O(1/N) что ли? :)

buddhist ★★★★★
()

1. создаём(в мыслях, в реализации это будет проверка) «интерфейс» который при выходе за длину строки даёт не_пробел.

текущая_длина=ноль

тек_поз=0;тек_поз<n;; смотрим сл_поз=тек_поз+текущая_длина+1 символ: это запредел тогда return текущая_длина // необязательная ветка это не_пробел тогда тек_поз=сл_поз

.....

короче когда набираем строку можно сканироть всплошную.

а вот когда скачем при поиске нового начала можно прыгать длиной текущей

если непробел значит между последним концом и новым местом заведомо не может быть длинее уже найденой если же пробел нужно смотреть между находить пробелы .

т.е первый пробел можно у новой строки искать всквозь а затем делать прыжки длиной уже найденой_текущей_максимальной.

qulinxao ★★☆
()
Ответ на: Идея алгоритма от four_str_sam

Интереснее, чем у меня. Размер шага можно брать и по макс. размеру последовательности (по крайней мере у меня все тесты пройдены с таким шагом).

/**
 * Подсчитывает пробелы слева и справа от символа (включая символ).
 *
 * @param str [in] -- указатель на символ.
 * @return длина последовательности пробелов.
 */
unsigned long
count_left_right_spaces (char* str)
{
  int left_spaces = 0, right_spaces = 0;

  for (unsigned long i = 1; ' ' == str[-i]; ++i)
    {
      left_spaces++;
    }

  for (unsigned long i = 0; ' ' == str[i]; ++i)
    {
      right_spaces++;
    }

  return left_spaces + right_spaces;
}

/**
 * Определяет длину самой большой последовательности пробелов
 * в данной строке.
 *
 * @param str [in] -- строка с пробелами.
 * @return длина последовательности пробелов.
 */
unsigned long
count_max_spaces (char* str)
{
  unsigned long max_spaces = 0;
  
  for (unsigned long i = 0, step = 1; i < strlen (str); i += step)
    {
      unsigned long max_spaces_in_sequence = 0;

      if (' ' == str[i])
        {
          max_spaces_in_sequence = count_left_right_spaces (&str[i]);
        }

      if (max_spaces_in_sequence > max_spaces)
        {
          max_spaces = max_spaces_in_sequence;

	  step = max_spaces;
        }
      
      if (max_spaces > strlen (str) - i)
        {
          /*
	    Количество оставшихся символов меньше длины самой
	    большой последовательности пробелов.
	    Т. е. большей последовательности гарантированно не будет.
          */
          break;
        }
    }

  return max_spaces;
}
Deleted
()
Ответ на: комментарий от buddhist

зависит от плотность пробелов.

т.е амортизационо О(logN) если плотность пробел 1/a где а>1 - т.е теория очередей и какая-то пуасонов процесс??

учитывая , что на некотором шаге тебе известна уже длина А не имеет смысл каждый раз набирать строки короче A и только в случае если по краям на растоянии A+1 пробелы нужно заглядывать внуть

это вроде кнута-мориса-прата приём.

в худшем вырожденом случае очевидно O(n)

однако практически амортизационно(по «естественным» строкам) O(что то похожее на лог или степень между корнем? и 1)

qulinxao ★★☆
()
Ответ на: комментарий от Deleted

В отличии от первого варианта тут таки есть баг. Править уже нельзя, поэтому кому интересно исправите сами.

Deleted
()

На 64-битной машине ты можешь за 1 раз обрабатывать 8 символов. Вот тебе и ускорение.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Deleted

i < strlen(str)
if (max_spaces > strlen(str) - i)

O(N^3).

@param str [in] — строка с пробелами.
@return длина последовательности пробелов.

Жабист. Ясно-понятно.

anonymous
()
Ответ на: комментарий от anonymous

O(N^2)

Self-fix. Но всё равно п[...]ц.

anonymous
()
Ответ на: комментарий от anonymous

i < strlen(str)
if (max_spaces > strlen(str) - i)

O(N^3).

Компилятор оптимизирует этот участок кода в первую очередь. Поэтому не стоит отбирать у него хлеб (хотя в некоторых случаях, когда компилиться необходимо без оптимизаций, это, конечно, нужно делать ручками).

Жабист. Ясно-понятно.

Ребятам с tianocore тоже не забудь сообщить о том, что они — жабисты (ибо doxygen != java).

Deleted
()
Ответ на: комментарий от Eddy_Em
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

uint16_t two_spaces = ' ' << 8 | ' ';
uint32_t four_spaces;
uint64_t eight_spaces;

int get_spaces(char *S){
	int cnt = 1, othercnt;
	uint64_t *u64p;
	S = strchr(S, ' ');
	if(!S) return 0;
	S++;
	u64p = (uint64_t*)S;
	while(*u64p++ == eight_spaces){
		printf("found 8 spaces\n");
		cnt += 8; S += 8;
	}
	while(*S++ == ' ')
		cnt++;
	if(!S) return cnt;
	othercnt = get_spaces(S);
	return (cnt > othercnt) ? cnt : othercnt;
}

int main(int c, char **v){
	if(c == 1){
		fprintf(stderr, "Использование: %s \"текст\"\n", v[0]);
		return 1;
	}
	four_spaces = ((uint32_t)two_spaces) << 16 | two_spaces;
	eight_spaces = ((uint64_t)four_spaces) << 32 | four_spaces;
	printf("Самая длинная последовательность пробелов: %d\n", get_spaces(v[1]));
	return 0;
}

./count "                                                                 65"
found 8 spaces
found 8 spaces
found 8 spaces
found 8 spaces
found 8 spaces
found 8 spaces
found 8 spaces
found 8 spaces
Самая длинная последовательность пробелов: 65
Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Выполняем по миллиону раз:

laptop-eddy> 02.08, 10:36 /tmp
time ./count "  2   3"  

real	0m45.135s
user	0m45.087s
sys	0m0.030s
laptop-eddy> 02.08, 10:39 /tmp
time ./count "         9                 17"

real	0m45.525s
user	0m45.550s
sys	0m0.003s
laptop-eddy> 02.08, 10:40 /tmp
time ./count "         9                 17         9"

real	1m6.457s
user	1m6.403s
sys	0m0.043s
laptop-eddy> 02.08, 10:42 /tmp
time ./count "         9                 17     5"

real	1m10.904s
user	1m10.873s
sys	0m0.053s

Eddy_Em ☆☆☆☆☆
()
Ответ на: Идея алгоритма от four_str_sam

Спасибо. Видать, это как раз то, что и имел ввиду автор.

Twissel ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

Что-то долго у тебя получилось. У меня (для Снова задачка (комментарий)):

...
...
  for (int i = 0; i < 1000000; ++i)
    {
      unsigned long max_spaces = count_max_spaces (argv[1]);
      printf ("Max spaces sequence length: %lu.\n", max_spaces);
    }

  return 0;
}


λ> gcc -Wall -std=c99 count_spaces.c -o count_spaces
λ> time ./count_spaces "  2   3" >>/dev/null
./count_spaces "  2   3" >> /dev/null  0,14s user 0,00s system 99% cpu 0,145 total
λ> time ./count_spaces "         9                 17" >>/dev/null
./count_spaces "         9                 17" >> /dev/null  0,18s user 0,00s system 99% cpu 0,184 total
λ> time ./count_spaces "         9                 17     5" >>/dev/null
./count_spaces "         9                 17     5" >> /dev/null  0,19s user 0,00s system 99% cpu 0,189 total
Deleted
()
Ответ на: комментарий от Eddy_Em

Благодарю. Мне как всегда понравилось. Рафинированный Си - это хорошо!

Twissel ★★★★★
() автор топика
Ответ на: комментарий от Deleted

Извини: ачипятался. Миллиард:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

uint16_t two_spaces = ' ' << 8 | ' ';
uint32_t four_spaces;
uint64_t eight_spaces;

int get_spaces(char *S){
	int cnt = 1, othercnt;
	uint64_t *u64p;
	S = strchr(S, ' ');
	if(!S) return 0;
	S++;
	u64p = (uint64_t*)S;
	while(*u64p++ == eight_spaces){
//		printf("found 8 spaces\n");
		cnt += 8; S += 8;
	}
	while(*S++ == ' ')
		cnt++;
	if(!S) return cnt;
	othercnt = get_spaces(S);
	return (cnt > othercnt) ? cnt : othercnt;
}

int main(int c, char **v){
	long i;
	if(c == 1){
		fprintf(stderr, "Использование: %s \"текст\"\n", v[0]);
		return 1;
	}
	four_spaces = ((uint32_t)two_spaces) << 16 | two_spaces;
	eight_spaces = ((uint64_t)four_spaces) << 32 | four_spaces;
	//printf("Самая длинная последовательность пробелов: %d\n", get_spaces(v[1]));
	for(i = 0; i < 1000000000; i++) get_spaces(v[1]);
	return 0;
}
Eddy_Em ☆☆☆☆☆
()
Ответ на: Идея алгоритма от four_str_sam

Шаг увеличивать не получится: все равно больше 8 символов за одну операцию ты не сравнишь! Разве что появятся 256-битные процессоры!

Но в целом — да, именно так, пожалуй, и надо делать: нашли пробел, сравнили следующую подстроку со строкой длиной N пробелов (где N — максимально найденная подстрока из пробелов). Если удовлетворительно — сравниваем дальше и обновляем N.

Вот только, как я уже говорил, проблемка в "векторном" сравнении: не умеют пока процессоры такого.

Еще вариант: распараллелить задачу, отдав каждому ядру по 1 потоку, работающему с частью текста. Затем слиянием вычислить нужное. Я думал таким образом ускорить алгоритм marching squares, но когда увидел, что и неоптимизированный работает миллисекунды на изображении в 16Мпикселей, понял, что рано еще.

Eddy_Em ☆☆☆☆☆
()

Всем еще раз спасибо за то, что быстро откликнулись и дали мне весомый повод для того, чтобы проснуться.

Загляну в топик попозже. Сейчас дела.

Twissel ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

Шаг увеличивать не получится: все равно больше 8 символов за одну операцию ты не сравнишь! Разве что появятся 256-битные процессоры!

Там дело не в сравнении, а в возможности найти среди символов последовательность больше текущей максимальной. То есть если у тебя текущая макс. последовательность 20, то не имеет смысла смотреть каждый из последующих символов. Но если есть большая последовательность, то она в любом случае попадет на шаг размером с текущую макс. последовательность.

p.s. Надо было сразу использовать обозначение буквой вместо «макс. последовательность»…

Deleted
()
Ответ на: комментарий от Eddy_Em

Извини: ачипятался. Миллиард:

Ага. Только вот неожиданность:

λ> time ./count_spaces "         9                 17     5" >>/dev/null
./count_spaces "         9                 17     5" >> /dev/null  19,12s user 0,00s system 100% cpu 19,113 total
λ> time ./count "         9                 17     5" >>/dev/null       
./count "         9                 17     5" >> /dev/null  21,95s user 0,00s system 100% cpu 21,936 total

Простое решение «в лоб» оказалось быстрее.

Deleted
()
Ответ на: комментарий от Deleted

А ты возьми посерьезней тестовые последовательности. На пару килобайт. И запускай миллион раз.

Мне просто лень было приличней делать.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em
λ> ./gen_kb_str.py 64                      
 1 11 1111111 1  11 1111  11 1 1 111 1 11  1 11111111111 11111 1%                                                                                      
λ> TestString=$(./gen_kb_str.py 4096)      
λ> time ./count $TestString >>/dev/null
./count $TestString >> /dev/null  7,70s user 0,00s system 100% cpu 7,702 total
λ> time ./count_spaces $TestString >>/dev/null 
./count_spaces $TestString >> /dev/null  7,14s user 0,00s system 100% cpu 7,138 total
λ> time ./count_spaces2 $TestString >>/dev/null
./count_spaces2 $TestString >> /dev/null  1,35s user 0,00s system 99% cpu 1,353 total

И опять, простое (count_spaces) быстрее.

p.s. А count_spaces2 это Снова задачка (комментарий).

p.p.s. Если распределение пробелов/не_пробелов сделать 3/1, то ситуация не меняется.

λ> ./gen_kb_str.py 64                
  1  1     1      1   1    1     1           1  1          1    %                                                                                      
λ> TestString=$(./gen_kb_str.py 4096)  
λ> time ./count $TestString >>/dev/null       
./count $TestString >> /dev/null  5,58s user 0,00s system 100% cpu 5,574 total
λ> time ./count_spaces $TestString >>/dev/null 
./count_spaces $TestString >> /dev/null  4,60s user 0,00s system 100% cpu 4,600 total
λ> time ./count_spaces2 $TestString >>/dev/null
./count_spaces2 $TestString >> /dev/null  0,84s user 0,00s system 99% cpu 0,840 total

Deleted
()
Последнее исправление: Deleted (всего исправлений: 2)
Ответ на: комментарий от Deleted

Баг, я так понимаю, в этом?

Ага.

С питоном перепутал? х)

Не, в питоне такое тоже будет неправильно.

Deleted
()
Ответ на: комментарий от Deleted

Разве? О_о а в чём тогда правильно? Я думал,

Там участок кода ищет пробелы левее от символа. В python '-1' ссылается на последний элемент массива. То есть если последние элементы — пробелы, то и их захватит. А если вся строка пробелы…

Deleted
()
Ответ на: комментарий от Deleted

Компилятор оптимизирует этот участок кода в первую очередь. Поэтому не стоит отбирать у него хлеб (хотя в некоторых случаях, когда компилиться необходимо без оптимизаций, это, конечно, нужно делать ручками).

Нет, не оптимизирует. У тебя строка внутри цикла может меняться. Hint: const char*

hateyoufeel ★★★★★
()
Ответ на: комментарий от Deleted

Ааа, вот что ты хотел сделать! Тогда ясно.

Deleted
()
Ответ на: комментарий от hateyoufeel

Hint: const char*

С этим согласен, если не меняется строка, то лучше сообщать об этом явно.

Нет, не оптимизирует.

Наркоман? Лови дизасм, если сам не осилил посмотреть как в действительности:

http://i.imgur.com/pl5mmf0.png

http://i.imgur.com/cITucMu.png

Надеюсь пояснения не нужны что там происходит?

Deleted
()
Ответ на: комментарий от Deleted

Кто наркоман? Ты наркоман! Если я нулевой байт внутри цикла в середину строки всуну, оптимизация с выносом strlen выдаст неправильный код.

hateyoufeel ★★★★★
()
Ответ на: комментарий от hateyoufeel

Если я нулевой байт внутри цикла в середину строки всуну, оптимизация с выносом strlen выдаст неправильный код.

Если ты будешь записывать что-то в строку, то оптимизации с выносом strlen просто не будет.

p.s. И ты опять забыл посмотреть как все происходит в действительности перед тем, как говорить чушь.

Deleted
()
Последнее исправление: Deleted (всего исправлений: 1)

Когда нашел строку пробелов длинной N, находя начало следующей проверяешь первый пробел и элемент через N позиций от него на то пробел ли он, если пробел то проверяешь от первого пробела до N и далее. Если на N+1 позиции не пробел, следовательно строка явно меньше предыдущей. Т.е. все строки пробелов меньше чем найденная проверяются по 2 элементам и чем больше длинна найденной строки тем быстрее идет проверка. В коде не могу, не умею писать код.

anonymous
()
Ответ на: Идея алгоритма от four_str_sam

С подсказки очевидно, что именно он и имеется в виду.

int is_space(char s) {return s == ' '?1:0;}//можно заинлайнить если что

int f(const char *s)
{
  enum {
    FORWARD,
    SPACE_COUNT
  } state = FORWARD;
  int len = strlen(s);
  int ret = 0;
  int local_ret = 0;
  int i = 0;
  while (is_space(s[i++])) {ret += 1;}//пробелы в начале удручают
  while (1) {
    switch (state) {
      case FORWARD:
        if (is_space(s[i])) {
          while (is_space(s[i])) {--i;}
          ++i;
          state = SPACE_COUNT;
          continue;
        }
        break;
      case SPACE_COUNT:
        if (is_space(s[i])) {
          local_ret += 1;
          ++i;
          continue;
        } else {
          if (local_ret > ret) {
            ret = local_ret;
          }
          local_ret = 0;
          state = FORWARD;
        }
        break;
    }
    if (i + ret > len) break;
    i += ret+1;
  }
  return ret;
}

nanoolinux ★★★★
()
Ответ на: комментарий от Eddy_Em

Обнаглею совсем, ибо не хочется напрягать извилины(а надо), зачем нужна эта строчка:

uint16_t two_spaces = ' ' << 8 | ' ';

Если в теле цикла, мы вроде как все равно считаем по 8 байт.

Не уловил...

Twissel ★★★★★
() автор топика
Последнее исправление: Twissel (всего исправлений: 1)
Ответ на: комментарий от Twissel

Мне неохота было копипастить. Если хочешь, пиши так:

uint64_t eight_spaces = ' ' << 56 | ' ' << 48 | ' ' << 40 | ' ' << 32 | ' ' << 24 | ' ' 16 << | ' ' << 8 | ' ';
Eddy_Em ☆☆☆☆☆
()

ШОК, РНР

Извиняюсь что немного не по теме, но не подскажете экспресс курс php-бойца? Нужно усилить знания на эту тему.

system
()
Ответ на: ШОК, РНР от system

[offtopic] Не знаю. Я когда-то начинал с этого Л.Веллинг Л. Томсон «Разработка веб-приложений с помощью PHP и MySQL». Солянка, конечно, сборная, но для вводного курса вроде пойдет. [/offtopic]

Twissel ★★★★★
() автор топика
Последнее исправление: Twissel (всего исправлений: 1)
Ответ на: комментарий от Deleted

strlen(str)

Компилятор оптимизирует этот участок кода в первую очередь.

Ты хоть в курсе, как работает strlen? Никакая оптимизация не избавится от O(N).

Засунув strlen в цикл, получаешь O(N^2).

anonymous
()
Ответ на: комментарий от anonymous

Ты хоть в курсе, как работает strlen?

В таком ключе стоит говорить только в том случае, когда твердо уверен в своих знаниях по рассматриваемому вопросу.

Никакая оптимизация не избавится от O(N).
Засунув strlen в цикл, получаешь O(N^2).

Нет изменения строки -> strlen можно вынести за пределы цикла. Что, собственно, компилятор и делает:

http://i.imgur.com/pl5mmf0.png http://i.imgur.com/cITucMu.png

Если туповат, то просто посчитай сколько раз встречается слово «strlen» на картинке.

Deleted
()

Просто мысли:

Проверяем середину строки, если пробел ищем границы (влево и вправо), если остатки строки больше найденной последовательности, рекурсивно проверяем и их. Т.о. нарезаем строку на части и быстро отсекаем не нужное.

sdio ★★★★★
()
Ответ на: комментарий от naszar

Прости за оффтоп, но чем такие красивые картинки из листинга нарисовал? Это IDA или что-то свободное?

IDA.

Из свободного radare классно рисует графы. Можешь попробовать его в качестве backend для bokken, если лень в консоли тыкать. Но он мне выдал непотребство вместо графа функции, потому IDA и воспользовался.

Deleted
()
Ответ на: комментарий от sdio

+1

задачка решается методом «деления пополам» и получается O(ln n)..а все битовые оптимизации делаются уже позже и вообще тут нах.ненужны.

ps код писать лень - отпуск, лето, дача..

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

А как сюда вписывается прием Кнута-Морриса-Пратта, все так же, просто начинаем с середины последовательности

Twissel ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.