NO

Author Topic: sort made with linked lists  (Read 352 times)

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
sort made with linked lists
« on: December 26, 2022, 05:11:08 am »
A small program to see how to sort a list of words using a linked-list.
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #1 on: December 26, 2022, 06:34:19 pm »
This is a new version that allocates a buffer before to sort, using VirtualAlloc.
When using this buffer I don't have to call malloc and to initialize the structure for each call.
Sorting 14130 words takes between 15/20 seconds.
If you have some ideas to be quicker I accept the suggestion.
The words to sort be in UTF-8.
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #2 on: December 26, 2022, 07:57:46 pm »
This version is improved and add a comparaison with qsort.
qsort takes 1 seconds and my function takes 14 seconds.

Here is the log file:

[26/12/2022 19:52:49] *** Log Started ***
[26/12/2022 19:52:50] Openning Log
[26/12/2022 19:52:50] Log Ready
[26/12/2022 19:52:50] Starting Sort
[26/12/2022 19:53:04] Ending Sort

[26/12/2022 19:53:04] Starting QSort
[26/12/2022 19:53:04] Ending QSort

[26/12/2022 19:53:04] Writing Result
[26/12/2022 19:53:05] Result Written
[26/12/2022 19:53:05] Closing Log file
[26/12/2022 19:53:05] *** Log Stoped ***
« Last Edit: December 27, 2022, 02:38:45 am by HellOfMice »
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #3 on: December 27, 2022, 04:58:28 am »
This new version takes 2/3 seconds for sorting 14130 words.
I have modified the structure to avoid lstrcpy but directly store the input string pointer to the structure
I make comparison on the first letter and if it is equal I use lstrcmp.
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #4 on: December 27, 2022, 09:27:58 am »
The previous versions rejected the string if it already was in the list.
This one doe not do that.

It sorts 18369 words in 4 seconds.

[27/12/2022 09:18:52] *** Log Started ***
[27/12/2022 09:18:52] Openning Log
[27/12/2022 09:18:52] Log Ready
[27/12/2022 09:18:52] Starting Sort
[27/12/2022 09:18:56] Ending Sort

[27/12/2022 09:18:56] Writing Result
[27/12/2022 09:18:56] Result Written
[27/12/2022 09:18:56] Closing Log file
[27/12/2022 09:18:56] *** Log Stoped ***
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #5 on: December 27, 2022, 01:14:06 pm »
This is the last version.
It is shorter and quicker.
4 seconds for 18369 words.

[27/12/2022 13:10:47] *** Log Started ***
[27/12/2022 13:10:47] Openning Log
[27/12/2022 13:10:47] Log Ready
[27/12/2022 13:10:47] Starting Sort
[27/12/2022 13:10:51] Ending Sort

[27/12/2022 13:10:51] Writing Result
[27/12/2022 13:10:51] Result Written
[27/12/2022 13:10:51] Closing Log file
[27/12/2022 13:10:51] *** Log Stoped ***
Kenavo

Offline John Z

  • Member
  • *
  • Posts: 531
Re: sort made with linked lists
« Reply #6 on: December 28, 2022, 01:12:39 pm »
Hi Hello....

Thanks got it. Going to learn from it.
I've used linked lists too so maybe I
can improve mine. You made significant
improvements along the way.

Thanks for contribution

John Z

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #7 on: December 28, 2022, 01:21:48 pm »
Don't forget that for sorting linked-lists a the worst solutions.
BTree is the best solution that I am trying to do without copying anyone.
Today I have sorted 23 324 lines in 7 seconds.

Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #8 on: December 29, 2022, 04:06:58 am »
Sorting 351213 words tooke 1 hour and 57 minutes.

[28/12/2022 20:00:19] *** Log Started ***
[28/12/2022 20:00:19] Openning Log
[28/12/2022 20:00:19] Log Ready
[28/12/2022 20:00:19] Starting Sort
[28/12/2022 21:57:40] Ending Sort

[28/12/2022 21:57:40] Writing Result
[28/12/2022 21:57:45] Result Written
[28/12/2022 21:57:45] Closing Log file
[28/12/2022 21:57:45] *** Log Stoped ***
Kenavo

Offline HellOfMice

  • Member
  • *
  • Posts: 20
  • Never be pleased, always improve
Re: sort made with linked lists
« Reply #9 on: December 29, 2022, 05:24:20 pm »
With this version I reduced by 35 minutes the time to sort more than 350000 words.
It takes 1h24 rather than 1h57 with the previous version.
This version only contents 1000 words in the file datas.c
I tried to measure the qsort function but with all the words it crashes.
Maybe it crashes because of bad parameters.
The tests I made tooke 4 seconds for 350000 words, strange...
It is very fast but I think it takes more time...

[29/12/2022 17:16:38] *** Log Started ***
[29/12/2022 17:16:38] Openning Log
[29/12/2022 17:16:38] Log Ready
[29/12/2022 17:16:38] Starting Sort
[29/12/2022 17:16:38] Ending Sort

[29/12/2022 17:16:38] Sorted 1000 words
[29/12/2022 17:16:38] Writing Result in file "Sort Result.txt"
[29/12/2022 17:16:38] Result Written
[29/12/2022 17:16:39] Closing Log file
[29/12/2022 17:16:39] *** Log Stoped ***
Kenavo