Unit SortList |
Copyright (c) DeltaSoft - Croatia
Classes |
TSortList - This it the sorted list class
Functions |
Types |
PSString
TData
TDataPtr
TListData
TListDataPtr
Constants |
Variables |
Functions |
Types |
PSString=^ShortStringThis class (with it's source) is given as freeware, with no guarantees. If it doesn't work, or puts your computer to smoke, destroys your data or whatever, DON'T BLAME ME ! Before using it in real life - TEST IT ! There's a test example "SortLst.dpr" ---------------------------------------------------- This class shows it's best performance with small lists (up to cca 5.000 records), but it can be used for large lists too. We have tested it on Cyrix P133+ (underclocked to 100 HMz) with 3 MB of free RAM, with this structure: 3 integers + 1 double field = 20 bytes, all key fields. Results with 100.000 records: * 1.) cca 160 sec to Create (and auto-sort) 100.000 records, (cca 2.5 MB of RAM allocated) * 2.) cca 150 sec to Delete every second record (50.000 records deleted) * 3.) cca 140 sec to Search for 100.000 records and create all that are missing (50.000 new records created, no new memory allocated) * 4.) cca 1 sec (one second) to Search for 100.000 records (all 100.000 records found) Results with 50.000 records: * 1.) cca 36 sec to Create (and auto-sort) 50.000 records, (cca 1.3 MB of RAM allocated) * 2.) cca 35 sec to Delete every second record (25.000 records deleted) * 3.) cca 28 sec to Search for 50.000 records and create all that are missing (25.000 new records created, no new memory allocated) * 4.) cca 1 sec (one second) to Search for 50.000 records (all 50.000 records found) Results with 10.000 records: * 1.) cca 1.4 sec to Create (and auto-sort) 10.000 records, (cca 250 KB of RAM allocated) * 2.) cca 0.7 sec to Delete every second record (5.000 records deleted) * 3.) cca 0.7 sec to Search for 10.000 records and create all that are missing (5.000 new records created, no new memory allocated) * 4.) cca 0.2 sec to Search for 10.000 records (all 10.000 records found) We used "SortLst.dpr" program for testing purposes, compiled sa Console application. ---------------------------------------------------- TSortList can manage records of any size, but it has few limitations: 1. Max index size (per record) is 255 bytes ! - The sum of bytes occupied by key fields must not exceed 255 bytes 2. Only this types of data can be used for key fields inside index: - Double (can be any other float type of 8 bytes, like TDateTime) - LongInt (can be any other integer type of 4 bytes) - Char (can be any other type of 1 byte, but it has to be converted to char for "FindKey") - Boolean (not recommended - you never know which value will represent "True") - ShortString [ size ] (has to be the last key field, only one per index) 3. Only one string field can be used as a key field for indexing, and it has to be the last key field. 4. For field that are not indexed, it doesn't matter that type you use. For non-indexed fields all types are allowed. 5. After posting a new record (Append - modify - Post), it is placed on his right place inside indexed list. If you need to change the key fields afterwards (after the first posting), you will have to Delete the record and create a new one, or the record will not be moved to new location inside a list. 6. After a record is deleted, no memory is being freed. But, if you append new records to your list, no new memory is needed until you exceed the amount of memory already allocated. This is because new records are filled in on places of previously deleted records. This method speeds-up delete operations and new insert operations (after delete), but if you use the list a long time, it is usefull to "EmptyTable" if you don't need the data inside it. After a call to "EmptyTable", all allocated memory is released. 7. Sorting is performed on the block of fields (all kinds of fields), so strings are not sorted alphabetically, and numbers are not sorted by value. The purpose of sorting is to arange data for fast Find operation, so you can check if a record with exact key fields already exists, but it is not arranged (sorted) for viewing. 8. If you move to another record before posting your modifications, all modifications to the record will be canceled (discarded). If you want to modify a record, you don't have to call "Edit" before. You just modify it, and then "Post" it. 9. When using FindKey, the values passed to it HAVE TO BE the same type as the key values. That is, zero for double is 0.0, and for integer is 0. Nil values are not allowed, because no type-conversation is made. That is because the class doesn't see the record structure (definition), so it can't make any type conversations. ---------------------------------------------------- For example, let's say we needed "MySortList" list, structured like this (3 fields, first 2 indexed): Field1 of type integer * (this one is the key field) Field2 of type double * (this is the second key field) Field3 of type double ------------------------- * Here's how we would define it's structure (any names can be used) :) type TMySortList=class(TSortList) // TMySortList is our List type Field1:integer; Field2, Field3:double; _:byte; // The EndMark field (every structure has to have it) end; var MySortList:TMySortList; // MySortList is our list variable ---------------- * Before you can use the list, you have to create (and define) it: MySortList:=TMySortList.Create; // Created * When created, you have to define it ("Field3" is the first non-indexed {non-key} field): with MySortList do Define(Field3,_); * If you want it to be indexed by all fields, call "Define" like this: with MySortList do Define(_,_); * And if you don't want it to be indexed ("Field1" is the first non-indexed field): with MySortList do Define(Field1,_); ----------------- * Work with the list (look at the "SortLst.dpr" example) ------------------ * After you've done using it, you have to destroy it: MySortList.Destroy; ---------------------------------------------------- If you find this class usefull and you have some ideas on increasing it's performance or adding additional feaatures that wouldn't slower down the performance, please contact me. My E-mail is
TData=array[0..MaxLongInt-1] of byte;
TDataPtr=^TDataData structure
TListData=array[1..MaxLongInt div 4] of integer;
TListDataPtr=^TListDataIndex structure
Constants |
Variables |