Data structure searches

# Search 150K lines(in a file) from 1 million lines (in a file)

BASH (N/A)
N/A
PYTHON (2 seconds)
#!/bin/python with open('150k-lines') as file1, open('one-mil-lines') as file2: a_lines = set(file1.read().splitlines()) b_lines = set(file2.read().splitlines()) for line in a_lines: if not line in b_lines: print "NOT OK %s" %(line) else: print "OK %s" %(line)
GOLANG (N/A)
No code yet.
C (600 milliseconds)
#include <stdio.h> #include <stdlib.h> #include <string.h> // Binary Search function int b_s(char *inArray[], int size, char *searchMe){ // Get start/mid/end of the array. int start = 0; int mid; int end = size - 1; // While start is less than end, set mid and search string. while(start <= end){ mid = (start + end)/2; if (strcmp(inArray[mid], searchMe) == 0){ // Found, return 0 return 0; } else if (strcmp(inArray[mid], searchMe) > 0){ // Not found and based on size reduce one from end to search. end = mid - 1; } else if (strcmp(inArray[mid], searchMe) < 0){ // Not found and based on size add one to start to search. start = mid + 1; } } // no result so return 1 return 1; } // Main. int main() { // Open files FILE *file = fopen("150k-lines", "r"); FILE *fileOne = fopen("one-mil-lines", "r"); // Set static array of 20 Mil. static char *sArray[20000000] = {0}; char line[256]; long int i = 0; // Store each line in one-mil-lines to an array. while(fgets(line, sizeof line, fileOne)!=NULL) { line[strlen(line) - 1] = '\0'; sArray[i]=strdup(line); i++; } // Set exit code to 0 int ext_code = 0; char ln[256]; // For each line in 150k-lines, perform binary search, // And print result. while(fgets(ln, sizeof ln, file) != NULL) { ln[strlen(ln) - 1] = '\0'; int f = b_s(sArray,i,ln); if(f == 0) { printf("OK - %d - %s\n",f,ln); } else { printf("NOT OK - %d, %s\n",f,ln); ++ext_code; } } // Exit. return ext_code; }