Что такое код lfind lsearch


Что такое код lfind lsearch

НАЗВАНИЕ
lsearch, lfind — последовательный поиск и обновление

ОПИСАНИЕ
Функция lsearch предназначена для выполнения последовательного поиска в соответствии с алгоритмом, описанным в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. — М.: Мир, 1978. Раздел 6.1, алгоритм S.

Функция lsearch возвращает указатель внутрь таблицы на искомые данные. Если данные не найдены, они добавляются в конец таблицы. Аргумент key указывает на объект данных, разыскиваемый в таблице (ключ поиска). Base указывает на первый элемент таблицы. Nelp — указатель на целое, содержащее текущее количество элементов в таблице. Это целое значение увеличивается на единицу, если в таблицу добавляются данные. Compar — функция сравнения, предоставляемая пользователем (например, функция strcmp). Функция сравнения вызывается с двумя аргументами — указателями на сравниваемые элементы. Она должна возвращать нулевое значение, если элементы равны, и значение, не равное нулю, в противном случае.

Функция lfind выполняет то же самое, что и функция lsearch, но не добавляет данные в таблицу при неудачном поиске, возвращая в этом случае пустой указатель NULL.

ПРИМЕЧАНИЯ
Указатели на ключ (key) и на первый элемент таблицы (base) должны иметь тип «указатель на элемент» и преобразовываться к типу «указатель на символ».

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

Хотя функция lsearch описывается как имеющая тип «указатель на символ», возвращаемое ею значение следует преобразовывать к типу «указатель на элемент».

ПРИМЕР Приведем фрагмент программы, который считывает цепочки символов в количестве, меньшем TABSIZE, и длиной, меньшей ELSIZE, и помещает прочитанные цепочки в таблицу, исключая дубликаты.

ДИАГНОСТИКА
Если искомый объект данных найден, то обе функции, lsearch и lfind, возвращают указатель на него. В противном случае функция lfind возвращает пустой указатель NULL, а функция lsearch возвращает указатель на новый, добавленный объект.

СЮРПРИЗЫ
Недостаток свободного пространства в таблице для добавления нового объекта данных может привести к непредсказуемым последствиям.

Выполняет ли POSIX lfind()/lsearch() лучше, чем цикл?

Do lfind / lsearch лучше, чем типичное решение для циклирования, которое проверяет каждый элемент до его соответствия? Есть ли специальный соус/причина, что эти функции существуют?

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

Но это, конечно, не проблема. Они завершают API других функций поиска, в частности bsearch и tsearch .

Вы можете знать только о производительности путем измерения. На вашем компьютере и на моем компьютере все по-разному отличается (у меня даже не может быть компилятор POSIX, который не может измерить lfind сам). По-разному между разными прогонами программы разные.

Итак, если вам нужно знать, попробуйте использовать методы lfind и homebrew и measure несколько раз.

В любом случае. C библиотечные функции, возможно, не были записаны в C . Если ваш lfind был написан в Python , я бы сказал, что он будет медленнее, чем метод доморощенного:)

Do POSIX lfind()/lsearch() работают лучше, чем петли вручную?

Do lfind / lsearch лучше, чем обычное циклическое решение, которое проверяет каждый элемент до его соответствия? Есть ли специальный соус/причина, что эти функции существуют?

Создан 11 сен. 10 2010-09-11 07:58:25 Matt Joiner


Почему? удобство. – Alexander Rafferty 11 сен. 10 2010-09-11 08:03:18

2 ответа

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

Но это, безусловно, не проблема с ними. Они дополняют API других функций поиска, в частности bsearch и tsearch .

Создан 11 сен. 10 2010-09-11 08:15:42 Jens Gustedt

Я прочитал исходный код для lfind/lsearch в eglibc-2.11.1, никаких специальных оптимизаций не было сделано вообще. Невозможность встроить — это самая большая проблема, как вы заявили. – Matt Joiner 12 сен. 10 2010-09-12 08:38:24

Вы можете знать только о производительности путем измерения. На вашем компьютере и моей машине все зависит от меня (возможно, даже у компилятора POSIX не может измерять lfind ). По-разному между различными прогонами программы.

Илон Маск рекомендует:  Asp написание процедур

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

В любом случае . C Функции библиотеки, возможно, не были написаны в C . Если ваш lfind был написан в Python , я бы держал пари, что он будет медленнее, чем метод доморощенного :)

Создан 11 сен. 10 2010-09-11 11:20:38 pmg

Что такое код lfind lsearch

НАЗВАНИЕ
lsearch, lfind — последовательный поиск и обновление

ОПИСАНИЕ
Функция lsearch предназначена для выполнения последовательного поиска в соответствии с алгоритмом, описанным в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. — М.: Мир, 1978. Раздел 6.1, алгоритм S.

Функция lsearch возвращает указатель внутрь таблицы на искомые данные. Если данные не найдены, они добавляются в конец таблицы. Аргумент key указывает на объект данных, разыскиваемый в таблице (ключ поиска). Base указывает на первый элемент таблицы. Nelp — указатель на целое, содержащее текущее количество элементов в таблице. Это целое значение увеличивается на единицу, если в таблицу добавляются данные. Compar — функция сравнения, предоставляемая пользователем (например, функция strcmp). Функция сравнения вызывается с двумя аргументами — указателями на сравниваемые элементы. Она должна возвращать нулевое значение, если элементы равны, и значение, не равное нулю, в противном случае.

Функция lfind выполняет то же самое, что и функция lsearch, но не добавляет данные в таблицу при неудачном поиске, возвращая в этом случае пустой указатель NULL.

ПРИМЕЧАНИЯ
Указатели на ключ (key) и на первый элемент таблицы (base) должны иметь тип «указатель на элемент» и преобразовываться к типу «указатель на символ».

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

Хотя функция lsearch описывается как имеющая тип «указатель на символ», возвращаемое ею значение следует преобразовывать к типу «указатель на элемент».

ПРИМЕР Приведем фрагмент программы, который считывает цепочки символов в количестве, меньшем TABSIZE, и длиной, меньшей ELSIZE, и помещает прочитанные цепочки в таблицу, исключая дубликаты.

ДИАГНОСТИКА
Если искомый объект данных найден, то обе функции, lsearch и lfind, возвращают указатель на него. В противном случае функция lfind возвращает пустой указатель NULL, а функция lsearch возвращает указатель на новый, добавленный объект.

СЮРПРИЗЫ
Недостаток свободного пространства в таблице для добавления нового объекта данных может привести к непредсказуемым последствиям.


Что такое код lfind lsearch

lsearch, lfind — linear search and update

SYNOPSIS

void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
int (*
compar)(const void *, const void *));
void *lfind(const void *
key, const void *base, size_t *nelp,
size_t width, int (*
compar)(const void *, const void *));

DESCRIPTION

The lsearch() function shall linearly search the table and return a pointer into the table for the matching entry. If the entry does not occur, it shall be added at the end of the table. The key argument points to the entry to be sought in the table. The base argument points to the first element in the table. The width argument is the size of an element in bytes. The nelp argument points to an integer containing the current number of elements in the table. The integer to which nelp points shall be incremented if the entry is added to the table. The compar argument points to a comparison function which the application shall supply (for example, strcmp()). It is called with two arguments that point to the elements being compared. The application shall ensure that the function returns 0 if the elements are equal, and non-zero otherwise.

The lfind() function shall be equivalent to lsearch(), except that if the entry is not found, it is not added to the table. Instead, a null pointer is returned.

RETURN VALUE

If the searched for entry is found, both lsearch() and lfind() shall return a pointer to it. Otherwise, lfind() shall return a null pointer and lsearch() shall return a pointer to the newly added element.

Both functions shall return a null pointer in case of error.

ERRORS

EXAMPLES

Storing Strings in a Table

This fragment reads in less than or equal to TABSIZE strings of length less than or equal to ELSIZE and stores them in a table, eliminating duplicates.

Finding a Matching Entry

The following example finds any line that reads "This is a test.".

Илон Маск рекомендует:  Поиск в базе данных

APPLICATION USAGE

The comparison function need not compare every byte, so arbitrary data may be contained in the elements in addition to the values being compared.

Undefined results can occur if there is not enough room in the table to add a new item.

RATIONALE


FUTURE DIRECTIONS

SEE ALSO

CHANGE HISTORY

First released in Issue 1. Derived from Issue 1 of the SVID.

Issue 6

The DESCRIPTION is updated to avoid use of the term «must» for application requirements.

Что такое код lfind lsearch

Standard C Library ( libc.a )

Syntax


Description

Warning: Undefined results can occur if there is not enough room in the table for the lsearch subroutine to add a new item.

The lsearch subroutine performs a linear search.

The algorithm returns a pointer to a table where data can be found. If the data is not in the table, the program adds it at the end of the table.

The lfind subroutine is identical to the lsearch subroutine, except that if the data is not found, it is not added to the table. In this case, a NULL pointer is returned.

The pointers to the Key parameter and the element at the base of the table should be of type pointer-to-element and cast to type pointer-to-character. The value returned should be cast into type pointer-to-element.

The comparison function need not compare every byte; therefore, the elements can contain arbitrary data in addition to the values being compared.

Parameters


Base Points to the first element in the table.
ComparisonPointer Specifies the name (that you supply) of the comparison function ( strcmp , for example). It is called with two parameters that point to the elements being compared.
Key Specifies the data to be sought in the table.
NumberOfElementsPointer Points to an integer containing the current number of elements in the table. This integer is incremented if the data is added to the table.
Width Specifies the size of an element in bytes.

The comparison function compares its parameters and returns a value as follows:

  • If the first parameter equals the second parameter, the ComparisonPointer parameter returns a value of 0.
  • If the first parameter does not equal the second parameter, the ComparisonPointer parameter returns a value of 1.


Return Values

If the sought entry is found, both the lsearch and lfind subroutines return a pointer to it. Otherwise, the lfind subroutine returns a null pointer and the lsearch subroutine returns a pointer to the newly added element.

Implementation Specifics

These subroutines are part of Base Operating System (BOS) Runtime.

The bsearch subroutine, hsearch subroutine, qsort subroutine, tsearch subroutine.

Donald E. Knuth. The Art of Computer Programming , Volume 3, 6.1, Algorithm S. Reading, Massachusetts: Addison-Wesley, 1981.

Searching and Sorting Example Program and Subroutines Overview in AIX Version 4.3 General Programming Concepts: Writing and Debugging Programs .

Что такое код lfind lsearch

lsearch, lfind — linear search and update

SYNOPSIS

void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
int (*
compar)(const void *, const void *));
void *lfind(const void *
key, const void *base, size_t *nelp,
size_t width, int (*
compar)(const void *, const void *));

DESCRIPTION

The lsearch() function shall linearly search the table and return a pointer into the table for the matching entry. If the entry does not occur, it shall be added at the end of the table. The key argument points to the entry to be sought in the table. The base argument points to the first element in the table. The width argument is the size of an element in bytes. The nelp argument points to an integer containing the current number of elements in the table. The integer to which nelp points shall be incremented if the entry is added to the table. The compar argument points to a comparison function which the application shall supply (for example, strcmp()). It is called with two arguments that point to the elements being compared. The application shall ensure that the function returns 0 if the elements are equal, and non-zero otherwise.

The lfind() function shall be equivalent to lsearch(), except that if the entry is not found, it is not added to the table. Instead, a null pointer is returned.

RETURN VALUE

If the searched for entry is found, both lsearch() and lfind() shall return a pointer to it. Otherwise, lfind() shall return a null pointer and lsearch() shall return a pointer to the newly added element.

Both functions shall return a null pointer in case of error.

ERRORS

EXAMPLES


Storing Strings in a Table

This fragment reads in less than or equal to TABSIZE strings of length less than or equal to ELSIZE and stores them in a table, eliminating duplicates.

Finding a Matching Entry

The following example finds any line that reads "This is a test." .

APPLICATION USAGE

The comparison function need not compare every byte, so arbitrary data may be contained in the elements in addition to the values being compared.

Undefined results can occur if there is not enough room in the table to add a new item.

RATIONALE

FUTURE DIRECTIONS

SEE ALSO

CHANGE HISTORY

First released in Issue 1. Derived from Issue 1 of the SVID.

Issue 6

The DESCRIPTION is updated to avoid use of the term «must» for application requirements.

Do POSIX lfind()/lsearch() работают лучше, чем петли вручную?

Do lfind / lsearch лучше, чем обычное циклическое решение, которое проверяет каждый элемент до его соответствия? Есть ли специальный соус/причина, что эти функции существуют?

Создан 11 сен. 10 2010-09-11 07:58:25 Matt Joiner

Почему? удобство. – Alexander Rafferty 11 сен. 10 2010-09-11 08:03:18

2 ответа

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

Но это, безусловно, не проблема с ними. Они дополняют API других функций поиска, в частности bsearch и tsearch .


Создан 11 сен. 10 2010-09-11 08:15:42 Jens Gustedt

Я прочитал исходный код для lfind/lsearch в eglibc-2.11.1, никаких специальных оптимизаций не было сделано вообще. Невозможность встроить — это самая большая проблема, как вы заявили. – Matt Joiner 12 сен. 10 2010-09-12 08:38:24

Вы можете знать только о производительности путем измерения. На вашем компьютере и моей машине все зависит от меня (возможно, даже у компилятора POSIX не может измерять lfind ). По-разному между различными прогонами программы.

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

В любом случае . C Функции библиотеки, возможно, не были написаны в C . Если ваш lfind был написан в Python , я бы держал пари, что он будет медленнее, чем метод доморощенного :)

Создан 11 сен. 10 2010-09-11 11:20:38 pmg

lsearch()

lsearch(), lfind() — linear searching routines

SYNOPSIS

DESCRIPTION

The functions lsearch(3) and lfind(3) provide basic linear searching functionality.

Base is the pointer to the beginning of an array. The argument nelp is the current number of elements in the array, where each element is width bytes long. The compar function is a comparison routine which is used to compare two elements. It takes two arguments which point to the key object and to an array member, in that order, and must return an integer less than, equivalent to, or greater than zero if the key object is considered, respectively, to be less than, equal to, or greater than the array member.

The lsearch(3) and lfind(3) functions return a pointer into the array referenced by base where key is located. If key does not exist, lfind(3) will return a null pointer and lsearch(3) will add it to the array. When an element is added to the array by lsearch(3) the location referenced by the argument nelp is incremented by one.

LSEARCH

lfind, lsearch − linear search of an array.

SYNOPSIS

DESCRIPTION

lfind() and lsearch() perform a linear search for key in the array base which has *nmemb elements of size bytes each. The comparison function referenced by compar is expected to have two arguments which point to the key object and to an array member, in that order, and which returns zero if the key object matches the array member, and non-zero otherwise.

If lsearch() does not find a matching element, then the key object is inserted at the end of the table, and *nmemb is incremented.

RETURN VALUE

lfind() returns a pointer to a matching member of the array, or NULL if no match is found. lsearch() returns a pointer to a matching member of the array, or to the newly added member if no match is found.

Илон Маск рекомендует:  Римская нумерация
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL