Fw: Array Empty Slots

Fw: Array Empty Slots

[Chris]

 Thank you very much for your response.
 The problem maybe is in the DBMS query.I am not a DBA guru but i cant find
 until now an atomic operation (query ) that can handle this kind of
 procedural algorithm.Do you have sth to suggest?
 Another problem is that in the next version of this application the C
 interface will go away and the application will be a Web based one.This is
a
 bigger problem cause php is much slower in array searching operations.I
have
 looked a lot of bench's for this subject and i dont see positive results.
 Do you know or have sth to suggest for the web based operation? Its gone be
 much more difficult to solve this problem because the bottleneck there,
 should not concern only the computer but the language and the algorithm
 also.Please if you have sth to suggest, can you include some source code
for
 benchmarking if its no trouble for you?



 Best regards,
 Chris.

Re: Fw: Array Empty Slots

[Chris]

Nice try, but this problem has always been a sigificant point for DBMS
applications, web based or not.
Maybe i should better explain you the problem. Suppose that we have this
array below:

array = [ 0,1,2,3,4,5,7,8,9,10];

Which is the quickest way to find the missing sequential number in a sorted
array of a fixed lenght???

Re: Fw: Array Empty Slots

[M.Baris Demiray]

[-- Attachment #1: Type: text/plain, Size: 1962 bytes --]


Hi Chris,

Chris wrote:
>  Thank you very much for your response.
>  The problem maybe is in the DBMS query.I am not a DBA guru but i cant find
>  until now an atomic operation (query ) that can handle this kind of
>  procedural algorithm.Do you have sth to suggest?

No, the algorithm is already in the DBMS. You should only SELECT the
records WHERE their values is empty. And that's what you need, array of
empty records. Take a look at the index hint in my previous reply.

>  Another problem is that in the next version of this application the C
>  interface will go away and the application will be a Web based one.This is
> a
>  bigger problem cause php is much slower in array searching operations.I
> have
>  looked a lot of bench's for this subject and i dont see positive results.>  Do you know or have sth to suggest for the web based operation? 

Sorry, neither i'm a web developer, nor this is the proper place to
discuss.

 > Its gone be
>  much more difficult to solve this problem because the bottleneck there,
>  should not concern only the computer but the language and the algorithm
>  also.Please if you have sth to suggest, can you include some source code
> for
>  benchmarking if its no trouble for you?

A basic benchmarking can be done with usual library functions and system
calls. For example, gettimeofday [1] system call can return milliseconds
sensitive and clock_gettime [2] function can return nanoseconds
sensitive time information. These sensitivity will be enough i think.

Write tiny array searching and database querying codes and get time
differences. These will give some idea.

Regards.

[1] man 2 gettimeofday
[2] man 3 clock_gettime

> 
>  Best regards,
>  Chris.

-- 
"You have to understand, most of these people are not ready to be
unplugged. And many of them are no inert, so hopelessly dependent
on the system, that they will fight to protect it."
                                                         Morpheus

[-- Attachment #2: baris.vcf --]
[-- Type: text/x-vcard, Size: 342 bytes --]

begin:vcard
fn:M.Baris Demiray
n:Demiray;M.Baris
org:Labris Teknoloji
adr:;;Teknokent Silikon Bina No:24 ODTU;Ankara;;06531;Turkey
email;internet:baris@labristeknoloji.com
title:Yazilim Gelistirme Uzmani
tel;work:+903122101490
tel;fax:+903122101492
x-mozilla-html:FALSE
url:http://www.labristeknoloji.com
version:2.1
end:vcard

Re: Fw: Array Empty Slots

[Luciano Moreira - igLnx]

I think you ll need a secondary data structure (maybe another array - 
but I prefer a linked list) to flag or store something that could to 
index your main data structure (your array).

Of course, you ll need to feed the secondary structure -- The main 
question: WHERE ? If you could answer this question maybe our can 
suggest you some ways.

Luciano


Chris escreveu:

>Nice try, but this problem has always been a sigificant point for DBMS
>applications, web based or not.
>Maybe i should better explain you the problem. Suppose that we have this
>array below:
>
>array = [ 0,1,2,3,4,5,7,8,9,10];
>
>Which is the quickest way to find the missing sequential number in a sorted
>array of a fixed lenght???
>
>-
>To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>
>  
>

Re: Fw: Array Empty Slots

[Luciano Moreira - igLnx]

I don't know the best amount of itens, but if you have a low avarage of 
empties slots, maybe is possible to use array as your secondary data 
structure - Although, it ins't the better choice.

The concept is based on having a index to all empties slots, thus you ll 
need a secondary array to store the index of the main array ponting to 
the empties slots.

As you can see, you ll need to search whole itens of the first array 
(then this array needs to be small) looking for index for empties slots, 
if you don't find "empty index" through a especial flag like as 
0xFFFFFFFF (32 bits integer), you will need to go to the end of the main 
array, then you ll need also a special index to point to the last item 
into the main array.

All changes in the main array should be followed by refreshing the new 
empty item into de "INDEX ARRAY", so, you ll need to refresh it on 
load_itens, on delete_item, on inset_item, etc.


THE CONCEPT:
------------
unsigned long nLastIndex;
unsigned lont INDEX_ARRAY[10];
unsigned lont DATA_ARRAY[1000000];

nLastIndex = 600000

INDEX_ARRAY           DATA_ARRAY (MAIN ARRAY)
[0]=2                 [0]=3425
[1]=6                 [1]=798
[2]=0xFFFFFFFF        [2]=<EMPTY>
[3]=1234              [3]=344542
[4]=10000             [...]
[5]=0xFFFFFFFF        [1233]=8797
[6]=500000            [1234]=<EMPTY>
[7]=0xFFFFFFFF        [1235]=63784
[8]=0xFFFFFFFF        [...]
[9]=0xFFFFFFFF        [9999]=19
                      [10000]=<EMPTY>
                      [10001]=789
                      [...]
                      [499999]=9865
                      [500000]=<EMPTY>
                      [500001]=456
                      [...]
                      [600000]=<EMPTY>
                      [600001]=<EMPTY>
                      [600002]=<EMPTY>
                      ...
 
Luciano


nanakos@wired-net.gr escreveu:

>I appreciate your time spent to reply to my question.
>If you have seen the previous posts(emails) , i have an application that
>uses  a C API and retrieves a huge sequential array from a DBMS but some
>slots are empty.We need to find the missing integers from the sequential
>sorted array, so that we can use those slots to fill them with data.
>At the time we speak i use a very very simple algorithm that searches
>sequentially the array and finds the first missing integer,then exits and
>uses the first missing value.But the main problem comes when there is no
>empty value at all ,then we use the n+1 value to store the data.But what
>if the array is bigger than 100000 or bigger.The bottleneck of the
>application is that point.The sequential search is not fast enough after
>some thousands of integers.Do you know an efficient and optimized
>algorithm to solve that problem?? It becomes really slow after i lock the
>DB tables.The second user waits for me to end my array search,retrieve my
>slot and then proceed with my data fill up.
>I am willing to make changes in the application,and follow up with your
>suggestion(s) if the solution can really solve the problem.Can you
>describe your solution with the second data structure( i prefer an array
>).What do u have in mind???
>
>
>Best regards,
>Chris.
>
>
>  
>
>>I think you ll need a secondary data structure (maybe another array -
>>but I prefer a linked list) to flag or store something that could to
>>index your main data structure (your array).
>>
>>Of course, you ll need to feed the secondary structure -- The main
>>question: WHERE ? If you could answer this question maybe our can
>>suggest you some ways.
>>
>>Luciano
>>
>>
>>Chris escreveu:
>>
>>    
>>
>>>Nice try, but this problem has always been a sigificant point for DBMS
>>>applications, web based or not.
>>>Maybe i should better explain you the problem. Suppose that we have this
>>>array below:
>>>
>>>array = [ 0,1,2,3,4,5,7,8,9,10];
>>>
>>>Which is the quickest way to find the missing sequential number in a
>>>sorted
>>>array of a fixed lenght???
>>>
>>>-
>>>To unsubscribe from this list: send the line "unsubscribe
>>>linux-c-programming" in
>>>the body of a message to majordomo@vger.kernel.org
>>>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>
>>>
>>>
>>>
>>>      
>>>
>>-
>>To unsubscribe from this list: send the line "unsubscribe
>>linux-c-programming" in
>>the body of a message to majordomo@vger.kernel.org
>>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
>>    
>>
>
>
>
>
>  
>