[algogeeks] Re: C Runtime malloc
This would be accurate for Linux. You'll find Windows, other Unix flavors, MSDOS, and rt/embedded OS's all use their own approaches. This is why I suggested getting several sources to study. The usual is that the malloc gets big blocks from the OS and has a separate algorithm for allocating small blocks from the big ones. Again, strategies differ. I have not studied malloc implementations for about 10 years, but when I did, the rotating first fit was common. It is a very simple scheme that is O(N) where N is the number of free blocks available, but it can be implemented to be probabilistically constant time under reasonable assumptions. The free blocks are doubly linked in a circular free list. This means that the smallest block that can be allocated by malloc must hold two pointers (so it's 8 or 16 bytes). There is a single search pointer S into the circular list. When malloc is called, S is advanced around the list until the first block big enough to satisfy the request, including a small header for the block, is found. If this search fails, a new big block is obtained from the operating system and chained to the free list, S is set to the new block, and the search is restarted. Of course, normally the available block will be bigger than the request. It is removed from the list, the requested piece is allocated by filling in the header, which is normally just the size of the request and a pointer to the previous block, which is needed later. A pointer to the byte following the header is returned. The left-over smaller block (if any) is returned to the free list. When free is called, the freed block is placed on the free list. Checks are made to see if contiguous blocks before and/or after are already free. If so, the contiguous blocks are merged. Clever design of the header and the double links make it possible to do this merging in constant time. There are many possible enhancements to reduce the O(N) worst case performance of malloc. Each has advantages and disadvantages. There are also considerations for multi-threading support. There are variations on policy of returning memory to the OS if an entire big block is free. Etc. Etc. As I said, you must study examples. On Aug 16, 1:51 am, Mihai Donțu mihai.do...@gmail.com wrote: On Monday 16 August 2010 06:48:56 Ashish Goel wrote: do u have a refenrce for that, i am more interested in knowing how heap manager intracts with VMM Have a look at this:http://mxr.mozilla.org/mozilla-central/source/memory/jemalloc/jemalloc.c Quoting from the Linux malloc(3) page: Normally, malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2). When allocating blocks of memory larger than MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the memory as a private anonymous mapping using mmap(2). MMAP_THRESHOLD is 128 kB by default, but is adjustable using mallopt(3). Allocations performed using mmap(2) are unaffected by the RLIMIT_DATA resource limit (see getrlimit(2)). mmap() being the interaction you are looking for ... -- Mihai Donțu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
You have a string say foobarfoo in which fo and oo aree repeated twice.You have to find all such repeated pairs in O(n) time,The string can only have alphanumeric elements in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
write the test cases for rectangle overlap. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how to implement TAIL command of unix.
the method of farword seek is inefficient. consider case of 10
lines and you want to display only 3-4 lines. better seek from end.
use a buffer[buf_size].
let size =filesize.
lc = 0;
while(lc = given line input)
{
fseek(fp, size);
if(size buf_size)
fread(fp, size, buffer);
else
fread(fp, size, buf_size);
parse buf_size for '\n'
if( \n is in buffer )
increment line counter(lc ++)
if(size buf_size)
size -= buf_size
}
// you know the size, read the buffer one by one and print it
OR
// you could have put them while reading on to stack and print it out
now
On Aug 15, 8:46 am, Dave dave_and_da...@juno.com wrote:
Enter the lines into a FIFO queue as you read them. After you have
enqueued n lines, dequeue a line every time you enqueue one, so that
the queue will contain the last n (or fewer) lines of the file.
Dave
On Aug 13, 1:13 pm, amit amitjaspal...@gmail.com wrote:
I am trying using fseek but somehow its not working?- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Reading large numbers?
How can I read a file which has 10^9 characters or more efficiently? -- Janani T -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Alternative merge
Please check link.
On Aug 15, 8:25 pm, Gene gene.ress...@gmail.com wrote:
http://groups.google.com/group/algogeeks/browse_thread/thread/f56bac6...
The best solution given there is O(n) with only constant additional
storage.
On Aug 15, 1:51 pm, Debajyoti Sarma sarma.debajy...@gmail.com wrote:
so what was the optimal solution found in the previous discussion?? give a
link
I don't remember the name of the thread...so only i posted this.
On 8/15/10, Gene gene.ress...@gmail.com wrote:
In fact this solution was suggested (without code) in the original
discussion.
It's O(n^2).
You're only re-ordering a constant number (4) of elements in each
recursive pass, and each pass requires O(n) time to execute. You also
need to assume your compiler will remove the tail recursion.
Otherwise it will also require O(n) space, which misses the whole
point of the problem.
On Aug 15, 12:29 pm, Debajyoti Sarma sarma.debajy...@gmail.com
wrote:
Array of 2n length is given {a1,a2,a3,...,an,b1,b2,b3,...,bn}
we have to make the array like as {a1,b1,a2,b2,a3,b3,...,an,bn}
without using extra buffer space.
here a solution i came up withhttp://codepad.org/ub5Ie4sI
I know this was discussed before .
But i want to know the time complexity of the code i have given(i m
confused)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] BFS of binary tree
BFS a binary tree but print the last row in reverse order. a /\ bc /\ d f OUTPUT-abcfd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Data Structure for URL matching
I'm not sure what you want. I have post a solution to search for wildcards in tries. Now you claim to do it better with TS-Trees. Do you know who to compute a reverse TS-Tree? And why don't you try first to code a radix-tree, which is a compressed trie and build then the reverse radix-tree? Here is a solution to code a radix-tree, crit-bit- tree, pat-tree with mininmal understanding of comupter science: http://www.codeproject.com/KB/string/pat_and_huff.aspx IMHO I'm not sure why a Ternary-Search-Tree should be faster then a Radix-Tree? If a radix tree is already a binary-tree version of the trie, then can you explain me the advantage of a ternary-search-tree? On Aug 15, 8:31 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Seems a gud idea . I have read we can do better with Ternary Search Trees .Can anybody has any idea about it? On Sun, Aug 15, 2010 at 11:44 PM, Chi c...@linuxdna.com wrote: What you may need is a reverse trie. You may take a look at this: http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit amitjaspal...@gmail.com wrote: In our indexes, we have millions of URLs each of which has a link to some page contents, that is, URL-contents. Now, suppose a user types a query with wild cards *, which represent 0 or multiple occurrences of any characters, how do you build the indexes such that such a type of query can be executed efficiently by finding all corresponding URLs-contents efficiently. For example, given a queryhttp://www.*o*ve* ou.com. You need to find iloveyou.com, itveabcu.com, etc. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Median of two arrays..
above algo isnt handling unequal length arrays,
On Aug 13, 10:06 pm, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
Check this code
int med1,med2;
void func(int a[], int x1, int x2, int b[], int y1, int y2){
int midx,midy;
if((y2-y1+1)==2)
{
med1=max(a[x1],b[y1]);
med2=min(a[x2],b[y2]);
return;}
midx=(x1+x2)/2;
midy=(y1+y2)/2;
if(a[midx]b[midy]){
x2=x2-(midy-y1);
y1=midy;
}else{y2=y2-(midx-x1);
x1=midx;}
func(a,x1,x2,b,y1,y2);
}
med1 and med2 are two medians.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
