11-13-2014
Quote:
Originally Posted by
DGPickett
I wrote a "locality of reference" sort once: mmap64() the file and start sorting by making 2 lists of one line, then a linked list of 2 lines sorted, twice, and then merge them, then again, then merge the two sets of 4, etc.
This seems to be what is classically called
merge sort. In the wikipedia article there are also its Landau symbols for runtime estimates.
I hope this helps.
bakunin
10 More Discussions You Might Find Interesting
1. UNIX for Dummies Questions & Answers
I am trying to understand the webserver log file for an error which has occured on my live web site.
The webserver access file is very big in size so it's not possible to open this file using vi editor. I know the approximate time the error occured, so i am interested in looking for the log file... (4 Replies)
Discussion started by: sehgalniraj
4 Replies
2. Shell Programming and Scripting
Hi All
I have approximately 10 files that are at least 100+ MB in size. I am importing them into a DB to output them to the web. What i need to do first is clean the files up so i dont have un necessary rows in the DB. Below is what the file looks like:
Ignore the <TAB> annotations as that... (4 Replies)
Discussion started by: caddyjoe77
4 Replies
3. UNIX for Dummies Questions & Answers
How do we check 'large files' is enabled on a Unix box -- HP-UX B11.11 (2 Replies)
Discussion started by: ranj@chn
2 Replies
4. UNIX for Dummies Questions & Answers
I was wondering how sort works.
Does file size and time to sort increase geometrically?
I have a 5.3 billion line file I'd like to use with sort -u I'm wondering if that'll take forever because of a geometric expansion?
If it takes 100 hours that's fine but not 100 days.
Thanks so much. (2 Replies)
Discussion started by: dcfargo
2 Replies
5. Shell Programming and Scripting
hello all,
kindly i need your help, i made a script to print a specific lines from a huge file about 3 million line. the output of the script will be about 700,000 line...the problem is the script is too slow...it kept working for 5 days and the output was only 200,000 lines !!!
the script is... (16 Replies)
Discussion started by: m_wassal
16 Replies
6. Shell Programming and Scripting
Hello everyone!
I have 2 types of files in the following format:
1) *.fa
>1234
...some text...
>2345
...some text...
>3456
...some text...
.
.
.
.
2) *.info
>1234 (7 Replies)
Discussion started by: ad23
7 Replies
7. UNIX for Dummies Questions & Answers
Hi all,
I have problem with searching hundreds of CSV files, the problem is that search is lasting too long (over 5min).
Csv files are "," delimited, and have 30 fields each line, but I always grep same 4 fields - so is there a way to grep just those 4 fields to speed-up search.
Example:... (11 Replies)
Discussion started by: Whit3H0rse
11 Replies
8. Solaris
Hello everyone. Need some help copying a filesystem. The situation is this: I have an oracle DB mounted on /u01 and need to copy it to /u02. /u01 is 500 Gb and /u02 is 300 Gb. The size used on /u01 is 187 Gb. This is running on solaris 9 and both filesystems are UFS.
I have tried to do it using:... (14 Replies)
Discussion started by: dragonov7
14 Replies
9. UNIX for Advanced & Expert Users
Hello all -
I am to this forum and fairly new in learning unix and finding some difficulty in preparing a small shell script. I am trying to make script to sort all the files given by user as input (either the exact full name of the file or say the files matching the criteria like all files... (3 Replies)
Discussion started by: pankaj80
3 Replies
10. Shell Programming and Scripting
Hello,
I have a very large file of around 2 million records which has the following structure:
I have used the standard awk program to sort:
# wordfreq.awk --- print list of word frequencies
{
# remove punctuation
#gsub(/_]/, "", $0)
for (i = 1; i <= NF; i++)
freq++
}
END {
for (word... (3 Replies)
Discussion started by: gimley
3 Replies
LEARN ABOUT DEBIAN
mtbl_sorter
MTBL_SORTER(3) MTBL_SORTER(3)
NAME
mtbl_sorter - sort a sequence of unordered key-value pairs
SYNOPSIS
#include <mtbl.h>
Sorter objects:
struct mtbl_sorter *
mtbl_sorter_init(const struct mtbl_sorter_options *sopt);
void
mtbl_sorter_destroy(struct mtbl_sorter **s);
mtbl_res
mtbl_sorter_add(struct mtbl_sorter *s,
const uint8_t *key, size_t len_key,
const uint8_t *val, size_t len_val);
mtbl_res
mtbl_sorter_write(struct mtbl_sorter *s, struct mtbl_writer *w);
struct mtbl_iter *
mtbl_sorter_iter(struct mtbl_sorter *s);
Sorter options:
struct mtbl_sorter_options *
mtbl_sorter_options_init(void);
void
mtbl_sorter_options_destroy(struct mtbl_sorter_options **sopt);
void
mtbl_sorter_options_set_merge_func(
struct mtbl_sorter_options *sopt,
mtbl_merge_func fp,
void *clos);
void
mtbl_sorter_options_set_temp_dir(
struct mtbl_sorter_options *sopt,
const char *temp_dir);
void
mtbl_sorter_options_set_max_memory(
struct mtbl_sorter_options *sopt,
size_t max_memory);
DESCRIPTION
The mtbl_sorter interface accepts a sequence of key-value pairs with keys in arbitrary order and provides these entries in sorted order.
The sorted entries may be consumed via the mtbl_iter interface using the mtbl_sorter_iter() function, or they may be dumped to an
mtbl_writer object using the mtbl_sorter_write() function. The mtbl_sorter implementation buffers entries in memory up to a configurable
limit before sorting them and writing them to disk in chunks. When the caller has finishing adding entries and requests the sorted output,
entries from these sorted chunks are then read back and merged. (Thus, mtbl_sorter(3) is an "external sorting" implementation.)
Because the MTBL format does not allow duplicate keys, the caller must provide a function which will accept a key and two conflicting
values for that key and return a replacement value. This function may be called multiple times for the same key if the same key is inserted
more than twice. See mtbl_merger(3) for further details about the merge function.
mtbl_sorter objects are created with the mtbl_sorter_init() function, which requires a non-NULL sopt argument which has been configured
with a merge function fp.
mtbl_sorter_add() copies key-value pairs from the caller into the mtbl_sorter object. Keys are specified as a pointer to a buffer, key, and
the length of that buffer, len_key. Values are specified as a pointer to a buffer, val, and the length of that buffer, len_val.
Once the caller has finished adding entries to the mtbl_sorter object, either mtbl_sorter_write() or mtbl_sorter_iter() should be called in
order to consume the sorted output. It is a runtime error to call mtbl_sorter_add() on an mtbl_sorter object after iteration has begun, and
once the sorted output has been consumed, it is also a runtime error to call any other function but mtbl_sorter_destroy() on the depleted
mtbl_sorter object.
Sorter options
temp_dir
Specifies the temporary directory to use. Defaults to /var/tmp.
max_memory
Specifies the maximum amount of memory to use for in-memory sorting, in bytes. Defaults to 1 Gigabyte. This specifies a limit on the
total number of bytes allocated for key-value entries and does not include any allocation overhead.
merge_func
See mtbl_merger(3). An mtbl_merger object is used internally for the external sort.
RETURN VALUE
If the merge function callback is unable to provide a merged value (that is, it fails to return a non-NULL value in its merged_val
argument), the sort process will be aborted, and mtbl_sorter_write() or mtbl_iter_next() will return mtbl_res_failure.
mtbl_sorter_write() returns mtbl_res_success if the sorted output was successfully written, and mtbl_res_failure otherwise.
05/29/2012 MTBL_SORTER(3)