1. Given the class below, design a method to shrink the capacity of array \"num\

Question

1. Given the class below, design a method to shrink the capacity of array "num" to its size. public class Numbers { private double [ ] num; private int capacity; private int size; : : } 2. Given the classes below, design a search method in the "People" class which finds all the "Person" objects in the "persons" that match a "name" and save their indices in "x". public class Person { private String name; private int age; : : } public class Numbers { private int [ ] num; private int capacity; private int size; : : } public class People { private Person [ ] persons; private int capacity; private int size; private Numbers x; : : } 3. Given the same classes in question 2, design a method in the "People" class which bubblesorts the "persons" in ascending order by "age". 4. Given the class below, design a method in the "Strings" class which generates an array of random strings using digits and alphabets. public class Strings { private String [ ] x; private int capacity; private int size; : : }

Explanation / Answer

Linearly growing arrays To reduce the number of realloc calls, you should allocate memory in chunks. Usually, length (the number of used items) and capacity (the number of allocated items) are stored with the array: typedef struct { ITEM * items; size_t length; size_t capacity; } LIST; void InitList(LIST * list) { memset(list, 0, sizeof(LIST)); } bool AddItem(LIST * list, ITEM item) { const size_t chunk_size = 1024; if (list->length >= list->capacity) { // Try to extend the array ITEM * new_items = (ITEM *)realloc(list->items, (list->capacity + chunk_size) * sizeof(ITEM)); if (!new_items) return false; list->items = new_items; list->capacity += chunk_size; } list->items[list->length++] = item; return true; } Remember that realloc does not free the old memory block when it fails. Hence you should check the returned value from realloc before assigning it to list->items, or else you will create a memory leak. The capacity variable is unnecessary. If you add the items one-by-one, you can resize the array when its size reaches the next chunk boundary: bool AddItem(LIST * list, ITEM item) { const size_t chunk_size = 1024; if (list->length % chunk_size == 0) { ITEM * new_items = (ITEM *)realloc(list->items, (list->length + chunk_size) * sizeof(ITEM)); if (!new_items) return false; list->items = new_items; } list->items[list->length++] = item; return true; } The chunk_size constant should be a power of two so that your compiler can replace the slow modulus division with logical AND. If you add more than one item, you could keep this invariant: capacity is always equal to length rounded to the next multiple of chunk_size. inline size_t IsPowerOf2(size_t num) { return ((num - 1) & num) == 0; } // Round to the next multiple of powerof2 inline size_t Ceil(size_t num, size_t powerof2) { assert(IsPowerOf2(powerof2)); return (num + powerof2 - 1) & -(intptr_t)powerof2; } bool NeedResize1(size_t length, size_t added_len, size_t chunk_size) { size_t capacity = Ceil(length, chunk_size); return length + added_len > capacity; } ITEM * AddItems(LIST * list, size_t added_len) { const size_t chunk_size = 1024; if (NeedResize1(list->length, added_len, chunk_size)) { ITEM * new_items = (ITEM *)realloc(list->items, Ceil(list->length + added_len, chunk_size) * sizeof(ITEM)); if (!new_items) return NULL; list->items = new_items; } ITEM * items = list->items + list->length; list->length += added_len; return items; } My formula There is a simpler formula: bool NeedResize2(size_t length, size_t added_len, size_t chunk_size) { assert(IsPowerOf2(chunk_size)); return ((-(intptr_t)length) & (chunk_size - 1)) capacity added_len > capacity - length added_len > (-length) & (chunk_size - 1) The formula requires 3 operations versus 4 in NeedResize1 (assuming powerof2 is a constant). It's equivalent to NeedResize1 when (length + added_len) fits into machine word. The formula from Hacker's Delight Hacker's Delight contains the following formula for checking if the range of addresses from length to length + added_len crosses boundary of a chunk: chunk_size - (length & (chunk_size - 1)) length >= list->capacity) { size_t new_capacity = (list->capacity capacity * 2; ITEM * new_items = (ITEM *)realloc(list->items, new_capacity * sizeof(ITEM)); if (!new_items) return NULL; list->items = new_items; list->capacity = new_capacity; } list->items[list->length++] = item; return true; } size_t CeilLog2(size_t x) { // clp2 function by Henry Warren, Jr. x -= 1; x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); #if __SIZEOF_SIZE_T__ == 8 || _WIN64 x |= (x >> 32); #elif !(__SIZEOF_SIZE_T__ == 4 || _WIN32) #error Unknown machine word size #endif return x + 1; } ITEM * AddItems(LIST * list, size_t added_len) { size_t initital_capacity = 16; if (list->length + added_len > list->capacity) { size_t new_capacity = CeilLog2(list->capacity + added_len); if (new_capacity items, new_capacity * sizeof(ITEM)); if (!new_items) return NULL; list->items = new_items; list->capacity = new_capacity; } ITEM * items = list->items + list->length; list->length += added_len; return items; } For example, to linearly grow an array to 1 million items, you need 977 realloc calls (when chunk_size = 1024). With the doubling algorithm, you need to reallocate the array only 16 times. It's possible to get rid of capacity variable in this case, but it does not make much sense. The array already wastes a lot of memory, so one machine word will not change anything. Variable-length arrays in C99 and other languages C99 Standard allows variable-length arrays: bool read_and_process_file(const char * file_name) { FILE * f = fopen(file_name, "r"); if (!f) return false; char file_content[get_file_size(f)]; // Variable-length array fread(file_content, 1, sizeof(file_content), f); // sizeof is not a constant! fclose(f); // Do something with file_content return true; }

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.