· Начало · Отвђтить · Статистика · Поиск · FAQ · Правила · Установки · Язык · Выход · WASM.RU · Noir.Ru ·

 WASM Phorum —› WASM.A&O —› Строковые сравнения

. 1 . 2 . >>

Посл.отвђт Сообщенiе


Дата: Июн 16, 2004 22:15:07

В моем ASN.1 парсере есть такой клочок кода:
				if(!strcmp(typeA, "small-molecule"))
				{
					if(!strcmp(dbA, "CAS"))
						strcpy(dbA, "CHEMICAL ABSTRACTS SERVICE");
					else if(!strcmp(dbA, "HTTP://ICCB.MED.HARVARD.EDU."))
						strcpy(dbA, "ICCB");
					else if(strcmp(dbA, "CHEMICAL ABSTRACTS SERVICE") &&
							strcmp(dbA, "LIGAND") &&
							strcmp(dbA, "KLOTHO"))
							ErrLogPrintf ("Unknown database %s for interaction %ld\n", dbA, bip->iid);
				}


Он мне не нравился никогда, но сегодня разонравился окончательно.
1) Это медленно.
2) Это плохо поддерживать - сложно добавлять, сложно модифицировать. Фигня, короче.

Сейчас думаю как можно улучшить. Может, кто поможет?


Дата: Июн 16, 2004 22:25:27

Попробуй через switch.. если можно (я этот я зыу не знаю но думаю он похож на Си)

PS^
А на асме можно или НЕТ ПОТРЕБНОСТИ ?


Дата: Июн 16, 2004 22:29:48

Это и есть С :)
В С нельзя делать switch для строк.
Или ты имеешь в виду что-то вроде конечного автомата по switch? Что-то типа словарика?
С буковки A по Z?


Дата: Июн 16, 2004 22:30:30

А на асме можно или НЕТ ПОТРЕБНОСТИ ?

Можно, но только для SPARC v9 :)


Дата: Июн 16, 2004 23:07:20

В принципе, придумал. Хеш от строки и обрабатывать в switch. Довольно шустро будет...


Дата: Июн 16, 2004 23:12:12

Я думаю так: если "шаблон" сравнения (т.е. толи просто найдено, толи найдено и то и другое, а третье не найдено) меняется от одного поиска к другому + варианты действия для выполненого условия тоже варируются, тогда если строк с которыми мы сраниваем действительно много, а не как впредложеном варианте, то есть резон сделать массив прилизительно такого содержания - 1 элемент (строка1функция1), 2 элемент (строка2функция1), 3 элемент (стока3&&строка4&&строка5функция2), затем напустить на этот массив код, разбирающий каждый элемент - это будет универсально и не громоздко. Что касается скорости, то минус твоей процедурки как мне кажется в strcmp и strcpy.


Дата: Июн 16, 2004 23:23:31

volodya
LEX?

Не люблю базы данных "ручками"...


Дата: Июн 16, 2004 23:38:35 · Поправил: Безпощадный даос

struct TOKEN_INFO
{
	char *pIdentifyingName_;// можно использовать хеш, 
							// если удастся придумать надежную хеш-ф-цию кот. работает быстрее чем strcmp
	char pFullname;
};

TOKEN_INFO tokens[MAX_TOKEN] = 
{
	{"CAS", "CHEMICAL ABSTRACTS SERVICE"}, 
	{"HTTP://ICCB.MED.HARVARD.EDU.", "ICCB"},
	{"LIGAND", 0},
	{"KLOTHO", 0},
// ...
};

bool CheckDB(char *dbA)
{
	for (int i = 0; strcmp(dbA, tokens[i].pIdentifyingName_) && i < MAX_TOKEN; i++);
	if (i < MAX_TOKEN)
	{
		if (tokens[i].pFullname) lstrcpy(dbA, tokens[i].pFullname);
		return true;
	}
	ErrLogPrintf ("Unknown database %s for interaction %ld\n", dbA, bip->iid);
	return false;
}


Дата: Июн 16, 2004 23:48:17

Ой-ой-ой, сколько накидали...

Mad_C
Твой алгоритм не понял. Надо иллюстрировать в коде.

captain cobalt
Намек не понял. Что такое "LEX" - не знаю. Если это лексический анализатор, то он тут при чем? 8-(

green
Понял. Нравится идея, но не нравится strcmp. В первую очередь потому, что список строк будет возрастать. И очень шустро.


Дата: Июн 16, 2004 23:55:13

volodya
я имел ввиду практически, то, что и показал green
дейтвительно - самое слабое место здесь strcmp.... :(((


Дата: Июн 16, 2004 23:57:26

strcmp убирается, т.к. есть стойкая хеш-функция, мы заменяем ее простым сравнением...
Другое дело, что я бы не против пойти даже дальше, заменив, скажем, структуру green на хеш-таблицу, что даст вычислительную сложность близкую к O(1)...


Дата: Июн 17, 2004 00:34:38

Так, переписал. Если кому любопытно:
struct db_data
{
	Uint4 db_hash;
	char *db_name_replacement;
};

static struct db_data databases[]=
{
	{230852619, 0},								/*GenBank*/
	{83970255, 0},								/*KLOTHO*/
	{84784676, 0},								/*LIGAND*/
	{21044, 0},									/*MOD*/
	{290340, 0},								/*BIND*/
	{52138901, 0},								/*CHEMICAL ABSTRACTS SERVICE*/
	{167764825, 0},								/*MMCIF HET GROUP DICTIONARY*/
	{31280387, 0},								/*CHEMIDPLUS*/
	{21044, "MOLECULE OBJECT DATABASE"},		/*MOD*/
	{231357796, 0},								/*EMBL-EBI MSD*/
	{87971861, 0},								/*MOLECULE OBJECT DATABASE*/
	{317298, 0},								/*ICCB*/
	{1121934, "ICCB"},							/*HTTP://ICCB.MED.HARVARD.EDU.*/
	{18275, "CHEMICAL ABSTRACTS SERVICE"},		/*CAS*/
	/*EOF marker*/
	{0, 0}
};

static void CheckInDBVocabulary(char *db)
{
	Uint4 hash = 0;	
	struct db_data *d_ptr;
	d_ptr = &databases[0];

	hash = ELFHash(db);

	while(d_ptr->db_hash)
	{
		if(hash == d_ptr->db_hash)
		{
			if(d_ptr->db_name_replacement)
				strcpy(db, d_ptr->db_name_replacement); 
			
			return;
		}
		d_ptr++;
	}
	ErrLogPrintf ("Unknown database %s met while parsing\n", db);
}


Теперь осталась только одна вещь, которая мне не нравится.
1) МЕДЛЕННО.
Решение:
Добавить функцию сортировки и держать уже сортированную копию статического массива в памяти и переписать функцию на бинарный поиск.


Дата: Июн 17, 2004 03:24:05 · Поправил: Quantum

green
int i должно быть снаружи цикла for.

volodya
Нравится идея, но не нравится strcmp.
Можно заменить на "myHash != tokens[i].hash". green сам предлагает такую замену (см. коммент).


Дата: Июн 17, 2004 15:48:17

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


Дата: Июн 17, 2004 18:08:43

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

. 1 . 2 . >>


Powered by miniBB 1.6 © 2001-2002
Время загрузки страницы (сек.): 0.048