Кодерский уголок

Дарю всем кому интересно: две макры на Си - сортировка с удалением дублей (на базе сортировки через кучу) и двоичный поиск с возвратом ближайшего меньшего элемента при отсутствии точного совпадения. Обе базированы на обычных сишных функциях сортировки и поиска из ядра Linux. Сделал макрами, т.к. очень хочется универсальности и очень не хочется терять время на вызовах функций сравнения и обмена местами.

Код:

/*
 *  Copyright (C) 2013  Рыжий Тигра aka redtigra
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

// xlatsort.h - macros for sort+uniq and approx bsearch
// based on Linux kernel 3.12.5 linux/lib/sort.c by Matt Mackall <mpm@selenic.com>,
//                                        bsearch.c by Tim Abbott <tabbott@ksplice.com>
//

#ifndef __xlatsort_h___
#define __xlatsort_h___

#ifdef __cplusplus
extern "C" {
#endif

#define XLAT_SORT( type, /* type */ base/* [] */, /* int */ num, \
    cmp_macro/* ( type, elem1, elem2 ) - ret: < 0 if ( elem1 < elem2 ) and so on */, \
    /* returns: */ /* int - number of unique items: */ out_num ) \
  do { \
    register int jn = -(num), ji = jn / 2 + 1, jc, jr, jj; \
    register type *t_arr = (base) - jn - 1; \
    type t_el; /* for swap */ \
    /* heapify */ \
    for ( ; ji <= 0; ji++ ) { \
      for ( jr = ji; jr * 2 - 1 > jn; jr = jc ) { \
        jc = jr * 2 - 1; \
        if ( ( jc > ( jn + 1 ) ) && \
            ( cmp_macro( type, t_arr[ jc ], t_arr[ jc - 1 ] ) > 0 ) ) \
          jc--; \
        if ( cmp_macro( type, t_arr[ jr ], t_arr[  jc ] ) <= 0 ) \
          break; \
        t_el = t_arr[ jr ]; t_arr[ jr ] = t_arr[ jc ]; t_arr[ jc ] = t_el; \
      } \
    } \
    /* sort */ \
    for ( jj = ji = jn + 1; ji < 0; ji++ ) { \
      t_el = t_arr[ 0 ]; t_arr[ 0 ] = t_arr[ ji ]; t_arr[ jj ] = t_el; \
      for ( jr = 0; jr * 2 - 1 > ji; jr = jc ) { \
        jc = jr * 2 - 1; \
        if ( ( jc > ( ji + 1 ) ) && \
            ( cmp_macro( type, t_arr[ jc ], t_arr[ jc - 1 ] ) > 0 ) ) \
          jc--; \
        if ( cmp_macro( type, t_arr[ jr ], t_arr[ jc ] ) <= 0 ) \
          break; \
        t_el = t_arr[ jr ]; t_arr[ jr ] = t_arr[ jc ]; t_arr[ jc ] = t_el; \
      } \
      if ( cmp_macro( type, t_arr[ 0 ], t_arr[ jj ] ) != 0 ) \
        jj++; \
    } \
    [COLOR="DarkRed"][B]if ( jj != 0 ) \
      t_arr[ jj ] = t_arr[ 0 ]; \[/B][/COLOR]
    (out_num) = jj - jn; \
  } while (0)

#define XLAT_BSEARCH( type, /* type */ key, /* type */ base/* [] */, /* int */ num, \
    cmp_macro/* ( type, elem1, elem2 ) - ret: < 0 if ( elem1 < elem2 ) and so on */, \
    /* returns: */ /* int - index of item found: */ less_ret, /* BOOL */ exact ) \
  do { \
    register type *t_arr = (base); \
    register size_t t_start = 0, t_end = (num), t_mid = t_start; \
    register int t_result; \
    (exact) = 0; \
    if ( t_start < t_end ) do { \
      t_mid = t_start + (t_end - t_start) / 2; \
      if ( ( t_result = cmp_macro( type, key, t_arr[ t_mid ] ) ) < 0 ) { \
        t_end = t_mid--; \
      } else if ( t_result > 0 ) { \
        t_start = t_mid + 1; \
      } else { \
        (exact) = 1; break; \
      } \
    } while ( t_start < t_end ); \
    (less_ret) = /* (base) + */ t_mid; \
  } while (0)

#ifdef __cplusplus
}
#endif

#endif // __xlatsort_h___

Доработки и оптимизации приветствуются.

Upd 2013/12/30:
ШУХЕР!!! В коде макры XLAT_SORT была ошибка, сегодня только обнаружил. Кто уже стянул - весьма советую стянуть ещё раз (исправление выделено жирным тёмно-красным) либо взять исправленную и оптимизированную версию в этом посте.

Upd 11 фев 2015:
Внёс ещё несколько поправок - исправленный исходник брать тут.

 

Не могу удержаться, но - преимущества и красота C во всей красе, это вам не сраный шаблон какой-нибудь.

 

Steel Rat, :-))))))) +65537!

 

Чёрт меня дери, если я понимаю, что там написано. А я ещё думал, что знаю C.

 

Geryon, если развернуть макрос и назвать переменные человеческими именами - всё станет намного понятнее. Тут мы видим типичный пример переинжиниринга, который даёт минимальный прирост производительности, но совершенно убивает понимание и возможность дебага. Такие жуткие вещи должны быть полностью скрыты от прикладного программиста. Собственно, они и скрыты, а Тигра, вот, вытащил. =)

 

Dimouse, не знаю, но в Питоне достаточно легко сделать биндинги к сишной либе, думаю за день ты сделаешь запросто.

 

Где-то так. Почти. :-) Если ими пользоваться именно как макрами, то скрытыми и останутся. :-)))))
Собственно, мне нужны были удаление дублей при сортировке и адрес ближайшего подходящего элемента при промахе в поиске. В готовом виде не нашёл, сочинять с нуля было влом, выдрал из ядра Linux сортировку и поиск и доколдовал "удаление дублей" и "ближайший подходящий". Поэтому получилось несколько... э... эклектично. :-)

PS. Кстати, угадай - как я в сортировке через кучу ухитрился ещё и удалять дубли, не перетаскивая уже отсортированное с места на место? :-)

 

Мне лень. =)

 

Steel Rat, а там всё просто - я додумался кучу строить не от левого края массива, а от правого (присмотрись - все индексы в массиве отрицательные!) и разбирать, соответственно, тоже слева направо. Тогда повторы выкидываются совершенно естественным образом, остаются только уникальные.

PS. Кстати, удаление дублей можно и отключать - например, так:

Код:

#define XLAT_SORT( type, /* type */ base/* [] */, /* int */ num, \
    cmp_macro/* ( type, elem1, elem2 ) - ret: < 0 if ( elem1 < elem2 ) and so on */, \
    [B][COLOR="Blue"]/* BOOL */ keep_doubles, \[/COLOR][/B]
    /* returns: */ /* int - number of unique items: */ out_num ) \
...............................................
      if ( [B][COLOR="Blue"]keep_doubles || ([/COLOR][/B] cmp_macro( type, t_arr[ 0 ], t_arr[ jj ] ) != 0 ) [B][COLOR="Blue"])[/COLOR][/B] \
        jj++; \
...............................................

А если cmp_macro() реализовать чисто макрой, а не функцией, то при keep_doubles != 0 компилятор в процессе оптимизации ещё и уберёт сравнение, получится чуууточку быстрее.

 

Рыжий Тигра, ну чтобы в долгу не остаться, на тебе хитрую мою функцию. Это функция проверки строки на соответствие маске, писал сам. =) В ней только операции сложения и сравнения, никаких выделений памяти. Других подобных функций не видел, не могу сказать, что моя лучше. Скорость замерял, результаты точно не помню, но помню, что разница в тысячные доли секунды во времени появилась на миллионах вызовов.

Код:

bool maskedCompare(const char* text, const char* mask)
{
	bool result = true;
	bool done = false;

	while ( !done )
	{
		const char* skipTo = NULL;

		switch (*mask)
		{
			case '*':
				++mask;
				skipTo = mask;
			break;

			case '?':
				++text;
				++mask;
			break;

			case 0:
				result = *text == *mask;
				done = true;
			break;

			default:
				if (*text != *mask)
				{
					result = false;
					done = true;
				}
				++text;
				++mask;
			break;
		}

		if ( skipTo != NULL )
		{
			do 
			{
				if (*skipTo == 0)
				{
					done = true;
					break;
				}

				if (*text == 0)
				{
					result = false;
					done = true;
					break;
				}
			} while ( *skipTo != *text++ );

			if (!done)
			{
				++mask;
			}
		}
	}
	return result;
}

 

Dimouse, внешне - очень качественный код у это китайца, очень аккуратно. Если бы мне было надо - я бы присмотрелся к нему, люблю красиво оформленный код. Обычно он и работает соответственно. Намекаю, смотри папочку examples. =)

 

Dimouse, да у меня сейчас питон даже не стоит. Я люблю Lua. =) Насколько я понимаю, то тебе надо запустить setup.py, он пропишет себя в packages, а потом уже можно будет запускать примеры. Сама либа xmp у тебя должна быть установлена. Я так понимаю - эта? Как обычно make, install.

 

Dimouse, ну в свойствах проекта просто делаешь цель - Dynamic Library. И всё. На выходе получишь два файла *.lib для линковщика и *.dll.
А тебе надо package Питонячий получить, это pyd файл. Или pyd это будет либа этого китаеса? Не помню. И отличается ли? Надо гуглить, я так навскиду не могу сказать. Я больше двух лет назад этим занимался.

 

Add new project - win32 dynamic link library.