powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный pwdgen
25 сообщений из 188, страница 2 из 8
Тяпничный pwdgen
    #38807798
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЗаймусь наконец алгоритмами Анатолий и Дмитрия C:
Раз уж изучать собрался, то замени в моем коде
perebor(int N)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
void perebor(int N) // все комбинации N символов
{
	// Инициализанция
	char* buf = (char*)malloc(N + 1);
	memset(buf, simb_first, N);
	buf[N] = 0;
	char* last = buf + (N - 1); // указатель на последний символ (младший разряд)
	// Перебор
	bool istcho = true;
	while(istcho) {
		printf("%s\n", buf);
		// следующая комбинация
		char* cur = last;
		while(true) { 
			(*cur)++;
			if(*cur <= simb_last) {
				break;
			} else {
				*cur = simb_first;
				cur--;
				if(cur < buf) {
					// все варианты перебраны
					istcho = false;
					break;
				}
			}
		}
	}
	free(buf);
}


Небольшие косметические изменения, для улучшения читабильности.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807800
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дмитрий ваш код я уже изучил, и уже использовал вашу идею в оптимизированном алгоритме :)
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807804
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryDima T,

мне показалось, что это выражение будет истинным, когда cur не будет принадлежать массиву buf.
все верно, именно это и проверяется
SashaMercuryПотому я и спросил, законно ли сравнивать указатели принадлежащие разным кускам памяти
Нельзя сравнивать указатели на элементы разных массивов. В данном случае массив один, т.е. один кусок памяти.

В принципе можно это
Код: plaintext
1.
2.
3.
cur--;
if(cur < buf) {
...}


заменить на
Код: plaintext
1.
2.
3.
if(cur == buf) {
...}
cur--;


perebor(int N) целиком
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
void perebor(int N) // все комбинации N символов
{
	// Инициализанция
	char* buf = (char*)malloc(N + 1);
	memset(buf, simb_first, N);
	buf[N] = 0;
	char* last = buf + (N - 1); // указатель на последний символ (младший разряд)
	// Перебор
	bool istcho = true;
	while(istcho) {
		printf("%s\n", buf);
		// следующая комбинация
		char* cur = last;
		while(true) { 
			(*cur)++;
			if(*cur <= simb_last) {
				break;
			} else if(cur == buf) {
				// все варианты перебраны
				istcho = false;
				break;
			} else {
				*cur = simb_first;
				cur--;
			}
		}
	}
	free(buf);
}

...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807809
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima_TНельзя сравнивать указатели на элементы разных массивов. В данном случае массив один, т.е. один кусок памяти.
но если cur будет меньше начала массива buf, то cur не будет принадлежать этому массиву, значит сравниваются начало массива, и элемент не принадлежащий ему. Разве не так ?
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807810
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вот конечный вариант, с использованием идеи Дмитрия по окончанию всех вариантов(только модифицированная идея, выделил желтым), и предложения Анатолия использовать fputs вместо printf. Осталось избавить от аллоцирования, нужно делать так, чтобы стартовая строка появлялась с использованием макроса, если это возможно.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
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.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//функция принимает строку, и устанавливает её в следующее значение.
//если функция возвращает NULL значит варианты закончились
char* set_next_string(char* cur, size_t p)
{
	while (*(cur + p - 1) == 'z')
		*(cur + p-- - 1) = 'a';
	if (p == 0)
		return NULL;
	
	*(cur + p - 1) += 1;
	return cur;
}

int view_all_combination(size_t p, FILE* out)
{
	char* start_s = (char*)malloc(p + 1);
	memset(start_s, 'a', p); *(start_s + p) = '\0'; //установка стартового значения
	do	//вывод в поток out всех вариантов
	{
		fputs(start_s, out);
		putc('\n', out);
	} while (set_next_string(start_s, p));

	free(start_s);
	return 1;
}

int view_diap(int begin, int end, FILE* out)
{
	for (int i = begin; i <= end; ++i)
		view_all_combination(i, out);
	return 1;
}

int main(int argc, char** argv)
{
	FILE* out = fopen("output.txt", "w");
	view_diap(1, 6, out);
	fclose(out);
	return 0;
}
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807815
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
В принципе можно это
Код: plaintext
1.
2.
3.
cur--;
if(cur < buf) {
...}


заменить на
Код: plaintext
1.
2.
3.
if(cur == buf) {
...}
cur--;




вот, в первом участке кода, вы сравниваете адреса памяти не из одного буфера (если подразумевается истина), а второй участок кода полностью мне нравится. Я знаю что могу указывать на участок памяти(1 адрес) сразу после массива, но про то я могу указывать на участок памяти до массива, не слышал, потому и спросил
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807824
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryDima_TНельзя сравнивать указатели на элементы разных массивов. В данном случае массив один, т.е. один кусок памяти.
но если cur будет меньше начала массива buf, то cur не будет принадлежать этому массиву, значит сравниваются начало массива, и элемент не принадлежащий ему. Разве не так ?
У тебя путаница в голове: cur это не элемент массива, а указатель на элемент массива (адрес в памяти), т.е. сравниваются адрес записанный в cur и адрес начала массива. Обращение к памяти по этим адресам не происходит.

cur это переменная хранящая адрес в памяти, который (по условиям алгоритма) должен указывать на элемент массива (проверяется что он не указывает). При этом cur может указывать за пределы массива - это не криминал, криминал прочитать/записать по адресу за пределами массива, т.е. нельзя использовать *cur когда cur указывает за пределы массива, но при этом можно использовать содержимое переменной cur.

Понятно или с картинками объяснить? Это надо четко понимать при работе с указателями.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807831
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TSashaMercuryпропущено...

но если cur будет меньше начала массива buf, то cur не будет принадлежать этому массиву, значит сравниваются начало массива, и элемент не принадлежащий ему. Разве не так ?
У тебя путаница в голове: cur это не элемент массива, а указатель на элемент массива (адрес в памяти), т.е. сравниваются адрес записанный в cur и адрес начала массива. Обращение к памяти по этим адресам не происходит.

cur это переменная хранящая адрес в памяти, который (по условиям алгоритма) должен указывать на элемент массива (проверяется что он не указывает). При этом cur может указывать за пределы массива - это не криминал, криминал прочитать/записать по адресу за пределами массива, т.е. нельзя использовать *cur когда cur указывает за пределы массива, но при этом можно использовать содержимое переменной cur.

Понятно или с картинками объяснить? Это надо четко понимать при работе с указателями.

Такой участок кода имеет место быть ?
Код: plaintext
1.
2.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - 10;
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807836
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima_TПонятно или с картинками объяснить? Это надо четко понимать при работе с указателями.

Дмитрий, я всё это прекрасно понимаю, Сообщество, и вы в том числе этому меня научили :)

K&R p.104Если P и Q указывают на
элементы одного и того же массива, то такие отношения, как <, >= и т.д., работают
надлежащим образом. Например,
P < Q
истинно, если P указывает на более ранний элемент массива, чем Q. Отношения == и
!= тоже работают. Любой указатель можно осмысленным образом сравнить на
равенство или неравенство с NULL. Но ни за что нельзя ручаться, если вы используете
сравнения при работе с указателями, указывающими на разные массивы. Если вам
повезет, то на всех машинах вы получите очевидную бессмыслицу. Если же нет, то
ваша программа будет правильно работать на одной машине и давать непостижимые
результаты на другой.

Diomidis Spinellis Code Reading: The Open Source PerspectiveNote that, although it is illegal to access elements outside those prescribed by an array's limits, ANSI C
and C++ allow the calculation of the address of the element immediately after the array's end. Calculating
the address of any other element outside the array limits is illegal and can lead to undefined behavior in
some architectures even if no actual access takes place. The address of the element beyond the end is
used as an indicator for marking the end of the range and iterating through it.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807850
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryТакой участок кода имеет место быть ?
Код: plaintext
1.
2.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - 10;


Теоретически да, но практически это потенциальная трудноотлавливаемая ошибка, если далее ошибочно будет использовано *temp и по этому адресу окажется реальная память.
При инициализации лучше использовать NULL, чтобы при ошибочном обращении гарантированно была ошибка обращения к несуществующей памяти.
Код: plaintext
1.
char* temp = NULL;



Если много вычесть, могут проблемы возникнуть. Запусти
Код: plaintext
1.
2.
3.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - 100000000;
printf(temp < buf ? "true\n" : "false\n");
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38807900
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне кажется, что вы говорите следующее. Пусть x имеет тим size_t, тогда для следующего участка кода

Код: plaintext
1.
2.
3.
4.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - x;//(1)
if(temp < buf) //(2)
...



строчки 1 и 2 будут корректны если x будет в диапазоне от 1 до 5, а если x>1000 то строчки 1 и 2 некорректны и мы можем наблюдать undefined behaviour. Я вам говорю, что в любом случае мы наблюдаем undefined behaviour, и привожу ссылки на K&R и Спинеллиса. Не говорю, что вы не правы, но пока я с вами не согласен
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808119
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ого сколько тут читать.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808128
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryОсталось избавить от аллоцирования
Надо понимать, где остановиться оптимизируя код.
Данная оптимизация не даст никакого прироста скорости, потому что на 100 млрд итераций несколько аллокаций никак не повлияют, а код наверняка будет хуже читаться.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808130
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury
Код: plaintext
1.
2.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - 10;


Я-бы так никогда не делал. Это за пределами аллоцированной памяти. Разные среды ведут
себя по разному в таком кейсе при попытке чтения/записи по указателю temp. В хорошем
варианте мы получит немедленный лопух с сообщением типа Segfault или "Программа выполнила
недопустимую...".

В плохом варианте мы будем очень долго и глючно работать пока разработчика не накажут
коллеги за лень и глупость или проклянёт заказчик, или будет пробита карма, или всемогущий
покарает болезнями и смертью.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808234
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот ключевая мысль твоей цитаты:
SashaMercuryK&R p.104... Но ни за что нельзя ручаться, если вы используете
сравнения при работе с указателями, указывающими на разные массивы. ...
Она про другое. В данном случае проверка выхода за пределы массива. И это не означает что там другой массив (там неизвестно что), это просто выход за пределы, не более того.
SashaMercuryМне кажется, что вы говорите следующее. Пусть x имеет тим size_t, тогда для следующего участка кода

Код: plaintext
1.
2.
3.
4.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - x;//(1)
if(temp < buf) //(2)
...



строчки 1 и 2 будут корректны если x будет в диапазоне от 1 до 5, а если x>1000 то строчки 1 и 2 некорректны и мы можем наблюдать undefined behaviour.
В данном случае (если x любое число) для 100% уверенности можно проверять обе границы, т.е. temp за пределами массива buf[10] проверяется так
Код: plaintext
1.
if(temp < buf || temp >= buf + 10) 


адрес buf гарантированно больше 0, т.к. по адресу 0 (он же NULL) нет реальной памяти, сделано специально чтобы инициализировать указатели "в никуда" значением NULL, для виндовса это адреса 0 - 65535 (для линукса 0-16777215 если не путаю), т.е. в твоем примере можно получить неопределенность при x>65535 (это минимум, реально еще больше).

т.е. при x < 65535 можно упростить проверку до if(temp < buf)
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808252
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonSashaMercury
Код: plaintext
1.
2.
char* buf = (char*)malloc(sizeof(char)* 10);
char* temp = buf - 10;


Я-бы так никогда не делал.
это родилось для обобщения правомерности применения конструкции
Код: plaintext
1.
if(temp < buf) //(2)


читай сначала :)
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808393
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tmaytonпропущено...

Я-бы так никогда не делал.
это родилось для обобщения правомерности применения конструкции
Код: plaintext
1.
if(temp < buf) //(2)


читай сначала :)
Это неважно. Про связь массивов и указателей все знают. Значит делать можно сравнения
в диапазоне аллоцированной памяти элементов массива.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808484
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, я рад что вы меня поняли.

У нас есть участок кода:
Код: plaintext
1.
2.
3.
T* buf=(T*)malloc(sizeof(T)*100);
T* a1=buf-1;
T* a2=buf-1000000;



Дмитрий, я вас правильно понимаю, вы говорите, buf можно сравнить с a1, но если сравнивать с a2, мы имеем undefined behaviour ?
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808485
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЭто неважно. Про связь массивов и указателей все знают. Значит делать можно сравнения
в диапазоне аллоцированной памяти элементов массива.
см. выше, речь о такой конструкции
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
char buf[3] = "aa";
{
  char* cur = buf + 1;
  while(true) {
    ... работаем с *cur
    cur--;
    if(cur < buf) {
      break;
    }
    ...
  }
}


после break следующая } закрывает область видимости cur, т.е. обращение к *cur невозможно.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808497
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskySashaMercuryОсталось избавить от аллоцирования
Надо понимать, где остановиться оптимизируя код.
Данная оптимизация не даст никакого прироста скорости, потому что на 100 млрд итераций несколько аллокаций никак не повлияют, а код наверняка будет хуже читаться.

Догадался ) Последний код в моем последнем сообщении с кодом. Вы можете проверить его на скорость пожалуйста ?
код
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
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.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//функция принимает строку, и устанавливает её в следующее значение.
//если функция возвращает NULL значит варианты закончились
char* set_next_string(char* cur, size_t p)
{
	while (*(cur + p - 1) == 'z')
		*(cur + p-- - 1) = 'a';
	if (p == 0)
		return NULL;
	
	*(cur + p - 1) += 1;
	return cur;
}

int view_all_combination(size_t p, FILE* out)
{
	char* start_s = (char*)malloc(p + 1);
	memset(start_s, 'a', p); *(start_s + p) = '\0'; //установка стартового значения
	do	//вывод в поток out всех вариантов
	{
		fputs(start_s, out);
		putc('\n', out);
	} while (set_next_string(start_s, p));

	free(start_s);
	return 1;
}

int view_diap(int begin, int end, FILE* out)
{
	for (int i = begin; i <= end; ++i)
		view_all_combination(i, out);
	return 1;
}

int main(int argc, char** argv)
{
	FILE* out = fopen("output.txt", "w");
	view_diap(1, 6, out);
	fclose(out);
	return 0;
}


PS По вашему алгоритму у меня остались вопросы, но я ещё подумаю. Кстати, а как вам идея "выключать" программу через определенное время, или когда файл будет определенного размера ? Мы исключили бы постоянную проверку, и проверяли бы размер файла, каждые 5 минут например(это сгодится при размере пароля более 10 символов, например)
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808503
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
речь идёт о такой конструкции .

SashaMercuryDima T
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
void perebor(int N) // все комбинации N символов
{
	// Инициализанция
	char* buf = (char*)malloc(N + 1);
        char* last = buf + (N - 1);
	// Перебор
	char* cur = last;
	
...			
	if(cur < buf) 
}



такая операция законна ?
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808511
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вообщем ладно, не хватало чтобы мы ещё тут поругались. Я подумаю, над вашими идеями, возможно я их просто не понимаю . Ваша идея хорошая, и мне понятна, я её использовал в конечной версии программы. Спасибо C: и спасибо за код, мне было интересно его читать(я даже пил компот, и разбирал его) :)

PS Код Анатолия ещё не разобрал, как писал раньше, потому отпишу позже.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808512
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SSВаша идея хорошая
идея, как понять, что дальше не нужно двигать стрелку, она очевидно лучше и быстрее(в общем случае) постоянного сравнения через strcmp.
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808513
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton, я рад что вы меня поняли.

У нас есть участок кода:
Код: plaintext
1.
2.
3.
T* buf=(T*)malloc(sizeof(T)*100);
T* a1=buf-1;
T* a2=buf-1000000;



Дмитрий, я вас правильно понимаю, вы говорите, buf можно сравнить с a1, но если сравнивать с a2, мы имеем undefined behaviour ?
Неправильно. Это проверка на выход за пределы массива.
Полная проверка выглядит так
Код: plaintext
1.
if(a2 < buf || a2 >= buf + 100)


но если заранее известно что шаги короткие, то можно упростить сравнение до
Код: plaintext
1.
if(a1 < buf)


При большом смещении упрощать нельзя, т.к. указатель это не что иное как адрес с типом беззнаковое целое, т.е. твое вычитание вызывает переполнение, равносильно такому
Код: plaintext
1.
2.
unsigned int buf = 123456;
unsigned int a2 = buf-1000000; // = 2^32 - 1 000 000 + 123 456 = ~4 000 000 000
...
Рейтинг: 0 / 0
Тяпничный pwdgen
    #38808521
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Коллеги. Почему-то напомнился сабж о выделении массивов с "хвостиками".
...
Рейтинг: 0 / 0
25 сообщений из 188, страница 2 из 8
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный pwdgen
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]