Перейти до вмісту

Алгоритм порівняння


Повідомлень в темі: 2

#1 tolkien

    Чайник

  • Користувачі
  • Pip
  • 7 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 06.11.2010 – 12:02

  • 2
Зіштовхнувся з проблемою. Потрібна функція яка буде порівнювати 2 стрічки. Суть проблеми ось у чому:
стандартна функція порівняння порівнює посимвольно і не враховує що в назві можуть бути цифри. Наприклад вона посортує так:
1
12
2
21
3

а має бути
1
2
3
12
21

Тут я знайшов досить ефективний алгоритм. Якщо обидві стрічки починаються з цифр то я, спершу, перевіряю кількість цифр, що йдуть послідовно і, якщо, в якісь стрічці менше, то значить вона більша, а якщо цифр однаково, тоді викликаю вже стандартну функцію для порівняння.
Але цифри можуть зустрічатися не тільки на початку стрічки, а будь де. Наприклад:

ABC1
ABC12
ABC2
ABC21
ABC3

це так як сортує зараз, а має бути:

ABC1
ABC2
ABC3
ABC12
ABC21

Тут, звичайно можна порівнювати подібним чином, після кожного символа порівнювати чи не йде цифра і тоді робити знову ці дії, що я описав вище. Але тоді функція порівняння вийде досить складною і час її виконання може бути в декілька раз більший. А це не допустимо, так як кількість порівнянь буде дуже велика. Допускається максимальне зниження швидкодії в 2 рази.

Можливо хтось стикався з подібною проблемою, а може комусь в голову прийде ефективніший алгоритм порівняння. Буду вдячний за всі ідеї.

#2 Amarok

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2350 повідомлень
  • Стать:Чоловік
  • Місто:Дубно -> Нетішин -> Київ -> New York

Відправлено 25.04.2011 – 03:12

Перегляд дописуtolkien (6.11.2010 05:02) писав:

Зіштовхнувся з проблемою. Потрібна функція яка буде порівнювати 2 стрічки. Суть проблеми ось у чому:
стандартна функція порівняння порівнює посимвольно і не враховує що в назві можуть бути цифри. Наприклад вона посортує так:
1
12
2
21
3

а має бути
1
2
3
12
21

Тут я знайшов досить ефективний алгоритм. Якщо обидві стрічки починаються з цифр то я, спершу, перевіряю кількість цифр, що йдуть послідовно і, якщо, в якісь стрічці менше, то значить вона більша, а якщо цифр однаково, тоді викликаю вже стандартну функцію для порівняння.
Але цифри можуть зустрічатися не тільки на початку стрічки, а будь де. Наприклад:

ABC1
ABC12
ABC2
ABC21
ABC3

це так як сортує зараз, а має бути:

ABC1
ABC2
ABC3
ABC12
ABC21

Тут, звичайно можна порівнювати подібним чином, після кожного символа порівнювати чи не йде цифра і тоді робити знову ці дії, що я описав вище. Але тоді функція порівняння вийде досить складною і час її виконання може бути в декілька раз більший. А це не допустимо, так як кількість порівнянь буде дуже велика. Допускається максимальне зниження швидкодії в 2 рази.

Можливо хтось стикався з подібною проблемою, а може комусь в голову прийде ефективніший алгоритм порівняння. Буду вдячний за всі ідеї.


радікс сорт котрий використовує каунтінг сорт має посортувати подібні стрінги за лінійний час
http://www.cprogramming.com/tutorial/compu...eory/radix.html
  • 0

#3 Amarok

    Старійшина

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 2350 повідомлень
  • Стать:Чоловік
  • Місто:Дубно -> Нетішин -> Київ -> New York

Відправлено 25.04.2011 – 04:59

Перегляд дописуAmarok (24.04.2011 21:12) писав:

радікс сорт котрий використовує каунтінг сорт має посортувати подібні стрінги за лінійний час
http://www.cprogramming.com/tutorial/compu...eory/radix.html


вибачаюсь, не лінійний час а кількість елементів помножити на кількість символів в елементі (кількість чисел на кількість їх цифр)
  • 0



Кількість користувачів, що читають цю тему: 1

0 користувачів, 1 гостей, 0 анонімних