diff options
| -rw-r--r-- | CMakeLists.txt | 3 | ||||
| -rw-r--r-- | include/common.h | 1 | ||||
| -rw-r--r-- | include/nem_ull.h | 1 | ||||
| -rw-r--r-- | src/common.c | 30 | ||||
| -rw-r--r-- | src/dfs.c | 4 | ||||
| -rw-r--r-- | src/main/nem_ull_shuffle.c | 43 | ||||
| -rw-r--r-- | src/main/online.c | 2 | ||||
| -rw-r--r-- | src/nem_ull.c | 47 |
8 files changed, 129 insertions, 2 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 03d1063..e646d55 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -59,11 +59,14 @@ include_directories (${INCLUDE_DIR}) add_library(uknapsack STATIC ${SRC_FILES}) add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack.c) add_executable(online ${MAIN_SRC_DIR}/online.c) +add_executable(nem_ull_shuffle ${MAIN_SRC_DIR}/nem_ull_shuffle.c) target_link_libraries(uknapsack_bin uknapsack) target_link_libraries(online uknapsack) +target_link_libraries(nem_ull_shuffle uknapsack) install(TARGETS uknapsack_bin DESTINATION bin) install(TARGETS online DESTINATION bin) +install(TARGETS nem_ull_shuffle DESTINATION bin) install(TARGETS uknapsack DESTINATION lib) install(FILES ${INCLUDE_FILES} DESTINATION include) diff --git a/include/common.h b/include/common.h index b188955..f00a269 100644 --- a/include/common.h +++ b/include/common.h @@ -17,5 +17,6 @@ double dist_items(struct item *, struct item *); int len_front(struct front_item *); int cmp_items_ratio(const void * a, const void * b); int cmp_items_random(const void * a, const void * b); +void shuffle_items(struct data *, int); #endif diff --git a/include/nem_ull.h b/include/nem_ull.h index fd1b829..5e86c1f 100644 --- a/include/nem_ull.h +++ b/include/nem_ull.h @@ -5,5 +5,6 @@ struct front_item * nem_ull(struct data *); struct front_item * nem_ull_step(struct front_item *, struct data *, int); +struct front_item * nem_ull_online_shuffle(struct data *, int); #endif diff --git a/src/common.c b/src/common.c index 7a8b316..5fc944e 100644 --- a/src/common.c +++ b/src/common.c @@ -111,3 +111,33 @@ int len_front(struct front_item * f){ for(N=0;f!=NULL;f=f->next,N++); return N; } + +/* Shuffle data items starting on a certain index, in place */ +void shuffle_items(struct data * d, int start) { + int i, ind; + struct item * new_items; + + if (start < 0) return; + if (start >= d->N) return; + + new_items = (struct item *)malloc(d->N * sizeof(struct item)); + + /* These stay the same */ + for(i = 0; i < start; i++) { + new_items[i].p = d->items[i].p; + new_items[i].w = d->items[i].w; + } + + /* Shuffle the rest */ + for(i = start; i < d->N; i++) { + ind = rand() % (d->N - i); + new_items[i].p = d->items[i+ind].p; + new_items[i].w = d->items[i+ind].w; + d->items[i+ind].p = d->items[i].p; + d->items[i+ind].w = d->items[i].w; + } + + /* Replace old array */ + free(d->items); + d->items = new_items; +} @@ -88,6 +88,8 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s * Free leaf; * Continue; */ + change++; + if(tree->depth == data->N) { front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL); front_last = front_last->next; @@ -100,8 +102,6 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s tree = tree->next; free(old); - change++; - continue; } diff --git a/src/main/nem_ull_shuffle.c b/src/main/nem_ull_shuffle.c new file mode 100644 index 0000000..e0996ba --- /dev/null +++ b/src/main/nem_ull_shuffle.c @@ -0,0 +1,43 @@ +#include <stdio.h> +#include <time.h> +#include <stdlib.h> +#include <string.h> +#include <sys/time.h> +#include "common.h" +#include "structs.h" +#include "nem_ull.h" + +int main(int argc, char * argv[]){ + struct data * data; + struct front_item * front = NULL; + + if(argc!=3){ + printf("Wrong number of arguments!\n"); + printf("Example usage: %s cut_point data_file\n", argv[0]); + return 0; + } + + data = input(argv[2]); + + struct timeval tv; + gettimeofday(&tv, NULL); + srand(tv.tv_sec + tv.tv_usec); + + /* Sort data */ + qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio); + + printf("%d\n", atoi(argv[1])); + clock_t t = clock(); + front = nem_ull_online_shuffle(data, atoi(argv[1])); + + /* Remove first item from front (only a placeholder) */ + t = clock() - t; + printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(front)); + + print_front(front); + + free_front(front); + free_data(data); + + return 0; +} diff --git a/src/main/online.c b/src/main/online.c index fbec660..7dec27c 100644 --- a/src/main/online.c +++ b/src/main/online.c @@ -13,6 +13,8 @@ int main(int argc, char * argv[]){ struct data * data; struct front_item * front = NULL; struct online_return ret; + ret.tree = NULL; + ret.front = NULL; if(argc!=6){ printf("Wrong number of arguments!\n"); diff --git a/src/nem_ull.c b/src/nem_ull.c index f08506b..6405fc2 100644 --- a/src/nem_ull.c +++ b/src/nem_ull.c @@ -1,4 +1,5 @@ #include <stdlib.h> +#include <stdio.h> #include "nem_ull.h" #include "structs.h" #include "common.h" @@ -16,6 +17,52 @@ struct front_item * nem_ull(struct data * d){ return begin; } +struct front_item * nem_ull_online_shuffle(struct data * d, int rand_i){ + struct front_item * front; + struct front_item * ret_front; + struct front_item * it; + struct front_item * tmp; + struct front_item * jt; + int i; + + ret_front = new_front_item(0,0,NULL,NULL); + front = new_front_item(0,0,NULL,NULL); + + for(i=0;i<d->N;++i){ + if (i == rand_i) { + shuffle_items(d, i); + } + front = nem_ull_step(front,d,i); + + it = ret_front; + jt = front; + while(it != NULL && jt != NULL) { + if(it->i.p == jt->i.p && it->i.w == jt->i.w) { + jt = jt->next; + if(it->next == NULL) break; + it = it->next; + } else if(it->i.p < jt->i.p || (it->i.p == jt->i.p && it->i.w < jt->i.w)) { + if(it->next == NULL) break; + it = it->next; + } else if(it->i.p > jt->i.p || (it->i.p == jt->i.p && it->i.w > jt->i.w)) { + tmp = new_front_item(jt->i.p, jt->i.w, it->prev, it); + tmp->time = jt->time; + tmp->prev->next = tmp; + tmp->next->prev = tmp; + jt = jt->next; + } + } + + for(; jt != NULL; jt = jt->next) { + it->next = new_front_item(jt->i.p, jt->i.w, it, NULL); + it->next->time = jt->time; + it = it->next; + } + } + + return ret_front; +} + struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){ unsigned long int i,l0t,l1t,n; double pmax; |