ReSQL.ru
     
powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Бинарный поиск в отсортированном векторе структур
12 сообщений из 12, страница 1 из 1
Бинарный поиск в отсортированном векторе структур
    #39715012
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Здравствуйте уважаемые Гуру!
Я не студент и не профи. Будьте пожалуйста великодушны.

Visual Studio 2013

Раньше для поиска использовал функцию std::find_if();
С++
Код: 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.
struct Account
	{
		string Acnt = "";
		.......
		.......
	};
	//Перегрузка оператора сравнения структуры Account 
	bool operator == (Account& lhs, std::string& rhs)
	{
		return lhs.Acnt == rhs ;
	}

vector<Account> vecAccounts;

static int GetIndexVector(vector<Account>& vecAccounts, const string value)
{
		
	vector<Account>::const_iterator it;
	it = std::find_if(vecAccounts.begin(), vecAccounts.end(), [value](Account& Item){ return  Item.Acnt == value; });
	if (it == vecAccounts.end()) return -1;
	size_t idx = it - vecAccounts.begin();

	return idx;				
};



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

Вектор отсортирован по полю Acnt
Попробовал сделать так, по аналогии с первым кодом
С++
Код: 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.
struct Account
	{
		string Acnt = "";
		.......
		.......
	};	
	//Перегрузка оператора сравнения структуры Account 
	bool operator < (Account& lhs, std::string& rhs)
	{
		return lhs.Acnt < rhs ;
	}

vector<Account> vecAccounts;

static int GetIndexVector(vector<Account>& vecAccounts, const string value)
{
		
	vector<Account>::const_iterator it;
	it = std::lower_bound(vecAccounts.begin(), vecAccounts.end(), value, 
    [value](const Account& Item) { return Item.Acnt < value; }); 
	if (it == vecAccounts.end()) return -1;
	size_t idx = it - vecAccounts.begin();

	return idx;				
};



Компилятор пишет ошибку и указывает на строку в библиотеке algorithm
"Ошибка 84 error C2064: результатом вычисления фрагмента не является функция, принимающая 2 аргументов c:\program files (x86)\microsoft visual studio 12.0\vc\include\algorithm 2514 1 "

Понимаю что накосячил , наверное с лямбда выражением, а может и не только с ним.
Укажите пожалуйста в чем косяк.
Только пожалуйста растолкуйте простым языком

Заранее благодарен.
...
Рейтинг: 0 / 0
09.10.2018, 16:25
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715017
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ArbitТолько пожалуйста растолкуйте простым языком

У твоей лямбды один параметр. Для Compare требуется два.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
09.10.2018, 16:40
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715257
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Dimitry Sibiryakov, Спасибо.

В общем получилось так (все скомпилировалось и работает)
С++
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
struct Account
	{
		string Acnt = "";
		.......
		.......
	};

static int GetIndexVector(const vector<Account>& vecAccounts, const string& value)
{
		
	vector<Account>::const_iterator it;
	it = std::lower_bound(vecAccounts.begin(), vecAccounts.end(), value, 
    [](const Account& Item, const string& value) { return Item.Acnt < value; });
	if (it == vecAccounts.end()) return -1;
	size_t idx = it - vecAccounts.begin();

	return idx;				
};



НО!
На тестовом цикле (Вектор предварительно отсортирован по полю Acnt )
std::find_if() - 11.085 сек
std::lower_bound() - 12,200 сек

линейный поиск структуры в векторе быстрее бинарного?!
Разве такое может быть?
Или я опять накосячил?
...
Рейтинг: 0 / 0
10.10.2018, 00:07
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715327
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ArbitНО!
На тестовом цикле (Вектор предварительно отсортирован по полю Acnt )
std::find_if() - 11.085 сек
std::lower_bound() - 12,200 сек

линейный поиск структуры в векторе быстрее бинарного?!
Разве такое может быть?
Или я опять накосячил?
Бинарный поиск в разы быстрее. Замеры времени корректно сделаны?
...
Рейтинг: 0 / 0
10.10.2018, 07:22
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715503
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Возможно где-то происходит неявное создание копий объектов.
Проверьте нет ли в Account конструкторов из строки которые объявлены без explicit или операторов преобразования типа в строку.
...
Рейтинг: 0 / 0
10.10.2018, 12:21
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715530
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Anatoly Moskovsky, Спасибо, Вы правы!
...
Рейтинг: 0 / 0
10.10.2018, 13:19
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715535
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Dima T, Спасибо
Чем лучше делать замер,
clock()?
или использовать функцию из библиотеки chrono -
chrono::high_resolution_clock::now();
...
Рейтинг: 0 / 0
10.10.2018, 13:24
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715612
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ArbitDima T, Спасибо
Чем лучше делать замер,
clock()?
или использовать функцию из библиотеки chrono -
chrono::high_resolution_clock::now();
Неважно чем. В виндовсе можно clock().
Я на другое намекал, можно случайно измерить так:
Код: plaintext
1.
2.
3.
4.
test1();
printf("test1 end. time %lld ms\n", clock());
test2();
printf("test2 end. time %lld ms\n", clock());
...
Рейтинг: 0 / 0
10.10.2018, 15:34
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39715704
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Dima T, Спасибо!
...
Рейтинг: 0 / 0
10.10.2018, 18:04
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39741754
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Здравствуйте уважаемые Гуру!

Помогите пожалуйста найти мой косяк
Только пожалуйста не пинайте сильно.

- Есть отсортированный вектор структур.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
struct Account
	{
		string Acnt = "";
		string Prnt = "";
		string AcntName = "";
		double BA[12];
		double OD[12];
		double OK[12];
		double EA[12];
		vector<Correspondent> Correspondents;
	};
vector<Account> Accounts;



- Вектор заполняется в цикле структурами на основе SQL запроса из базы данных с сортировкой по текстовому полю Acnt .

Код: plsql
1.
SELECT Acnt, field1, field2, ... FROM Accounts ORDER BY Acnt;


- В этом поле находятся данные в следующем формате (для примера)::
"010"
"20"
"202"
"402-53"
"722-02-78"
Значения могут содержать только цифры и знак "-"

Фрагмент вектора
201
202
203
204
205
...
Ищу, например, структуру с полем поиска равным - "2025", или "202-53" которых нет в векторе
Получаю в результате индекс структуры со значением "203" в обоих случаях
хотя должен получить -1

Если ищу структуру со значением имеющимся в векторе , то все нормально


Вот функция которой проверяю наличие или отсутствие структуры в векторе
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
static int GetIndexVectorAccounts(const vector<Account> &table,  const string &value, int idxBegin = -1)
		{			
			vector<Account>::const_iterator it;
			it = std::lower_bound(table.begin(), table.end(), value, [](const Account &Item, const string &value) { return Item.Acnt < value; });
			if (it == table.end()) return -1;
			size_t idx = it - table.begin();
			return idx;

		};


Заранее благодарен всем откликнувшимся
...
Рейтинг: 0 / 0
02.12.2018, 20:31
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39741820
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Так и должно работать
https://en.cppreference.com/w/cpp/algorithm/lower_bound Return value

Iterator pointing to the first element that is not less than value, or last if no such element is found.

Добавь проверку найденного
Код: plaintext
1.
if (it == vecAccounts.end() || it->Acnt != value) return -1;
...
Рейтинг: 0 / 0
03.12.2018, 07:43
| Ответить | Цитировать | Написать  
Бинарный поиск в отсортированном векторе структур
    #39741839
Arbit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arbit
Гость
Dima T, спасибо огромное!
Добавь проверку найденного
if (it == vecAccounts.end() || it->Acnt != value ) return -1;

Да, вот этой части в проверке и не хватало
...
Рейтинг: 0 / 0
03.12.2018, 09:25
| Ответить | Цитировать | Написать  
12 сообщений из 12, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Бинарный поиск в отсортированном векторе структур
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&fpage=15&tid=2017709]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 43ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 46ms
get tp. blocked users:
 2ms
others: 253ms
total:  390ms
созд. / загр.: 390ms
x
x
Закрыть


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