nlogn's log :: 천천히 달리기

you don’t need 40′000 levenshtein calls

Simon proposes using a dictionary to match mistyped URLs with real ones. I’d probably like the idea better if I actually understood it. Still using Levenshtein can be a bit easier than using a spell checker responsively.

Easier, but slow. I used existing implementation by Magnus Lie Hetland and made a test with 245 blog titles using a simple script. 100 iterations on aging powerbook produced:

1.766s, 29.152s, 9.399s (min, max, avg)

Average time to calculate distance between randomly chosen title and rest of them is 9.4 seconds, which is far too much to be useful. And there’s not even 250 of them.

There are two obvious ways to speed things up. Since minimum distance is at least as much as a difference in length of both strings, there’s no point in calculating it when difference already exceeds a limit we chose.

The other trick took into an account that Levenshtein’s algorithm of two strings of comparable length has complexity of O(n2) and that my blog titles are form quite sparse space. If strings are longer than a certain limit (I arbitrarily chose 10 letters), then first calculate edit distance on a small sparse substring and then calculate the real distance only if first one was close enough.

When I made 1000 iterations of randomly chosen title using only first test, I got following results:

0.003s, 0.284s, 0.167s (min, max, avg)

However, if I used both checks, the same 1000 iteration test got me:

0.003s, 0.162s, 0.027s (min, max, avg)

So, two simple checks can speed up search up to 350 times. Not bad, but I’m not happy. This is certainly fast enough for a personal website or sites where site structure effectively divides searching to relatively small sets of possible hits, but there are plenty of sites where it would be too slow.

Search.h

//선언
int linearSearch(int *array, int size, int value);
int linearSearchSort(int *array, int size, int value);
int binarySearch(int *array, int size, int value);

#pragma warning(disable:4996)
#include <stdio.h>


int linearSearch(int *array, int size, int value)
{
 int i;
 for(i=0; i<size; i++)
 {
  if(array[i] == value)
  {
   printf("횟수 : 성공[%d번]\n", i);
   
   return i;
  }
 }
 printf("횟수 : 실패[%d번]\n", i);
 
 return -1;
}
int linearSearchSort(int *array, int size, int value)
{
 int i;
 for(i=0; i<size; i++)
 {
  if(array[i] >= value)
  {
   if(array[i] == value)
   {
    printf("횟수 : 성공[%d번]\n", i);
    return i;
   }
   else
   {
    break;
   }
  }
 }
 printf("횟수 : 실패[%d번]\n", i);
 return -1;
}
int binarySearch(int *array, int size, int value)
{
 int i, left, right, middle;
 left = 0, right = size-1;
 for(i=0; left<=right; i++)
 {
  middle = (left+right) / 2;
  if(array[middle] == value)
  {
   printf("횟수 : 성공[%d번]\n", i);
   return middle;
  }
  if(array[middle] < value)
  {
   left = middle+1;
  }
  else
  {
   right = middle-1;
  }
 }
  printf("횟수 : 실패[%d번]\n", i);
  return -1;
}

 
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
void printArray(int *array, int size);
int cmpAsc(const void *p1, const void *p2);
int cmpDsc(const void *p1, const void *p2);
void main(void)
{
 int array[11] = { 87, 41, 36, 71, 98, 56, 28, 45, 50, 11, 63 };
 
 printf("원본 : ");
 printArray(array, 11);
 qsort(array, 11, sizeof(array[0]), cmpAsc);
 printf("오름 : ");
 printArray(array, 11);
 qsort(array, 11, sizeof(array[0]), cmpDsc);
 printf("내림 : ");
 printArray(array, 11);
}
void printArray(int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  printf("%d ", array[i]);
 }
 printf("\n");
}
int cmpAsc(const void *p1, const void *p2)
{
 return *(int*)p1 - *(int*)p2;
}
int cmpDsc(const void *p1, const void *p2)
{
 return cmpAsc(p2, p1);
}

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "Sort.h"



void fillArray(int *array, int size);
void printArray(const int *array, int size);
void bubbleTest(const int *array, int size);
void selectionTest(const int *array, int size);
void insertionTest(const int *array, int size);
void heapTest(const int *array, int size);
void mergeTest(const int *array, int size);
void quickTest(const int *array, int size);
void main(void)
{
 int *array=NULL;
 int i, size;
 srand((unsigned) time(NULL));
 //초기화
 size = 4096;
 array = malloc(size*128*sizeof(int));
 //저속 정렬
 printf("[저속 정렬]\n");
 for(i=0; i<4; i++)
 {
  fillArray(array, size);
  printf("개수 : %d\n", size);
  bubbleTest(array, size);
  selectionTest(array, size);
  insertionTest(array, size);
  printf("\n");
  size *= 2;
 }
 //고속 정렬
 printf("\n[고속 정렬]\n");
 for(i=0; i<4; i++)
 {
  fillArray(array, size);
  printf("개수 : %d\n", size);
  heapTest(array, size);
  mergeTest(array, size);
  quickTest(array, size);
  printf("\n");
  size *= 2;
 }
 free(array);
}
void fillArray(int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  array[i] = rand() * rand();
 }
}
void printArray(const int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  printf("%10d ", array[i]);
  if(i%7 == 6)
  {
   printf("\n");
  }
 }
 printf("\n");
}
void bubbleTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 bubbleSort(temp, size);
 end = clock();
 printf("버블 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void selectionTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 selectionSort(temp, size);
 end = clock();
 printf("선택 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void insertionTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 insertionSort(temp, size);
 end = clock();
 printf("삽입 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void heapTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 heapSort(temp, size);
 end = clock();
 printf("힙   : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void mergeTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 mergeSort(temp, size);
 end = clock();
 printf("합병 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void quickTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int)+4);
 temp[size] = INT_MAX;
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 quickSort(temp, size);
 end = clock();
 printf("퀵   : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}