<commit_before>partitioned-hash-join
=====================

This script computes the intersection of two 1.3 GB large files with 100 million entries each. The resulting intersection of the two sets is saved in a separate file `result.txt`. 

A single entry of the input file is of the format `A1234567890\r\n`. Two entries are equal if the numeric part of the entries are equal. For example is `A1234567890` equal to `B1234567890`.

The problem is that this program must not use more than 50 MB of RAM.

The zipped input files can be found here:

- [file1.txt](http://www2.informatik.hu-berlin.de/~wandelt/DWDM/file1.zip)
- [file2.txt](http://www2.informatik.hu-berlin.de/~wandelt/DWDM/file2.zip)

If you don't want to work on the complete set while developing, you can easily create smaller files with the following command:


`$ cat file1.txt | head -1000000 > 1m.txt`

This creates a file with only 1 million entries.


## todo

- make script more generic
  - don't hard-code file names
  - pass files as arguments when invoking the script
- if possible, make it faster
  - try lower number of buckets without hitting memory limit
- test on delphi
- finish README (how to invoke script)<commit_msg>Update README.<commit_after>partitioned-hash-join
=====================

This is a homework solution for the following problem.

Given two **1.3 GB** large files with 100 million entries each, find the intersection of those files. The program must not use more than **50 MB** of RAM.

A single entry of the input files is of the format `A1234567890\r\n`. Two entries are equal if the numeric part of the entries are equal. For example is `A1234567890` equal to `B1234567890`.

The zipped input files can be found here:

- [file1.txt](http://www2.informatik.hu-berlin.de/~wandelt/DWDM/file1.zip)
- [file2.txt](http://www2.informatik.hu-berlin.de/~wandelt/DWDM/file2.zip)

As the name of the project suggests, the problem is solved using a partitioned hash join algorithm. 

# Running the script

Make sure the script is executable:

`$ chmod +x partitioned_hash_join.py`

Invoke the script, passing the files it should find the intersection for as arguments:

`$ ./partitioned_hash_join.py -r file1.txt -s file2.txt`

# Development

If you don't want to work on the complete set while developing, you can easily create smaller files with the following command:

`$ cat file1.txt | head -1000000 > 1m.txt`

This creates a file with only 1 million entries. The script runs in a reasonable amount of time with smaller file sizes.
{'fraction_non_alphanumeric': 0.09105304829770387, 'fraction_numerical': 0.04275534441805225, 'mean_word_length': 4.064128256513026, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6042258', 'n_tokens_mistral': 812, 'n_tokens_neox': 722, 'n_words': 342}