Page 2 of 2 FirstFirst 12
Results 11 to 19 of 19
  1. #11
    Join Date
    Jun 2003
    Posts
    150
    Quote Originally Posted by Kwest View Post
    In terms of searching an array it would be faster than say a linked list but when working with larger amounts a data a linked list would be preferred over a dynamic array. This is due to the nature of dynamic arrays needing to be doubled in size when reaching max capacity. When it reaches max capacity I have to allocate a new array, copy over the old data and then add a new element. With a linked list you never have to worry about this issue it takes the same amount of time each time I add a new element.
    Actually with large amounts of data the array still wins out even with the need to copy to new array. Arrays are much more cache friendly and iterating through large sets of data to perform operations on the data. This is because data is pulled in by chunks. When you access memory to read or write to, you grab the data plus several pieces of data next to it. If the data's already in cache it doesn't need to go do a look up. This is called a cache hit. Having the computer go look for something in system memory and bring it into cache is called a cache miss.

    Knowing how your data is going to grow can reduce the amount of times you need to resize the array, you can't always rely on std::vector's default behavior. There's ways of altering it and then there's times when you just have roll your own implemenation.

    In Reply to Zelosh's inquiry on data structures.

    Now as far as data structures are, they are basically ways of organizing data in a way that is relevant to a solution to a problem. Typically you see data organized into lists(arrays, linked list, etc.), tables(list of lists basically), trees (where the data is organized in some hierarchy) or graphs(data is linked to other data directly and you create paths to other bits of data). The concept of data structures alone is a huge topic(entire books you can kill an elk by dropping one on it have been written on the subject).


    Some examples you may have seen of as data structures. Lists are pretty common so there's no need to really give examples.

    Tables you can find used in dictionaries, data bases, path find algorithms for more efficient look ups. Basically each data entry has either an already determined key or is generated based on a data value and that key determines which list and its position the item is stored in. For instance in a path finding algorithm I have the position where I'm at. I can input that position into the table and get back a list of positions I can go to from that position. The coordinates get converted into a hash value which is just an index number leading to particular list. Then I can just go through each element in that one list to and compare it to my coordinates to find which one stores the list of potential places to move. If I stored all positions possible in one list I would have potentially search through a lot more data to find the list I'm looking for.

    Trees are all over the place. One place they are used is in spatial partitioning, which is breaking space(1,2,3 or however many dimensions you want) up into smaller areas linked to larger areas. A great examples a place's address. It has the building number, which is part of a street, which is part of a city, which contained with a county, which contained within a state/province, which is contained within a country, which is on a continent, which is on a planet, which is in a star system, which is in a quadrant, which withing a galaxy, which is in a universe, which is in a ball a slobbering baby is chewing on, which is in a place...okay I've gone too far.


    Graphs can be used for creating networks. Such examples are a navigation network to help with path finding. Each node in the graph represents a point that is reachable and each node has a list of adjacent node points.
    Last edited by Edge Damodred; 04-06-2012 at 08:34 PM.

  2. #12
    Join Date
    Mar 2009
    Location
    Bellevue, WA
    Posts
    803
    When inserting/deleting an element from the end of a list be it a dynamic array or a linked list the algorithm is 0(1) a dynamic array however is an amortized 0(1) analysis meaning that it will take into account for worst case scenarios, which can be extremely resource heavy,such as reaching the end of a list and having to resize and copy the data (which is an expensive process compared to inserting a single element at the end of linked list) hopefully though as you said, you can implement your own version and understand how your programs data will grow which can make this data structure very efficient in terms of deletion and insertion at the end of a list. The dynamic array is definitely much faster for accessing elements as this is an 0(1) analysis as you can get at your data simply with an index while the linked list is much poorer in this facet as it's an 0(n) analysis since we have to always start at the beginning of the list and move through it to get to the object were looking for.

    When it comes to inserting and removing elements from the middle of list, the winner here is the linked list since you can easily drop a element in and connect it to the rest of the list without having to recopy the data. If an element needs to be added to the middle of the dynamic array you would have to copy all the elements beyond the index into a temp array insert the element at it's index and then copy the temporary array with the data that follows the insertion, same goes for removal of an element from the middle of the dynamic array. So here the linked list is 0(1) and the DynArray 0(n). It's just as bad with a dynamic array when you have to insert an element at the beginning of the list where it's much faster to insert at the beginning of a linked list. So depending on what your purpose is they both have there advantages and disadvantages. As you said though you can minimize the expensive resizing of the dynamic array by understanding the growth of your data which is why the insertion at the end of a dynamic list is 0(1) amortized.
    " Imagination is the preview of life's coming attractions " - Albert Einstein
    " If you can't explain it simply, you don't understand it well enough." - Albert Einstein

    My Website: http://www.gamedevlounge.com/

    If any post is informative please provide positive feedback by clicking the star below.

  3. #13
    Join Date
    Jun 2011
    Location
    Westerville, OH
    Posts
    9

    Progress yay!

    Okay! So I got this almost figured out...

    I didn't know how cin held input it was given or anything like that, so I was really confused at first, but I realized cin could just process one character at a time even if they had already been entered ahead of time.

    The array has a character assigned to each slot, and each time there is a check to see if that slot contains '0' or is about to cause overflow. I feel like I'm cheating here a bit, as I'm making the user input specifically when the string should end, but I didn't know how else to let the program know that the string was finished. From there I just made it equal NULL instead of '0' to terminate the string.

    arr_add is my function for lengthening the array by creating a new one and readjusting the old pointer. The size changes in increments of 10 rather than doubling, since I figured the numbers would get unnecessarily big by doubling, wasting space.

    arr_print works just fine, easy peasy thanks to what Kwest said.

    PROBLEM 1: I can't delete the old arrays in the heap. Technically it's irrelevant in terms of this project, since Windows will figure out I'm done with it, but I'm not okay with having memory leaks. I commented out delete[] ptro; which I had originally thought would use the address in the pointer to simply delete the old array, and then I'd return the new address to the original function where my original variable, ptr, would simply gain the new address and shrug off the old deleted one. It doesn't work, I get bad memory allocation, which is odd considering it works so long as I don't use the delete command!! I can't just change the name of ptr, it would mess up my loops and function calls.

    PROBLEM 2: The output is great but there's no spaces. This is a minor problem, but I'm not sure how I'd get around it if I really needed to.

    Code:
    #include <iostream>
    
    using namespace std;
    
    char *arr_add(char *ptro, int *length) {
    	*length += 10;
    	char *ptrn = new char[*length];
    
    	for(int i = 0; i < *length; i++)
    		ptrn[i] = ptro[i];
    
    	//delete[] ptro;
    	return(ptrn);
    }
    
    void arr_print(char *ptr, int length) {
    	if(ptr == NULL) return;
    	
    	cout << "Hello, ";
    	for(int i = 0; i < length-1; i++)
    		cout << ptr[i];
    	cout << endl;
    }
    
    int main() {
    	int length = 10;
    	char *ptr = new char[length];
    
    	cout << "Enter your name, then type 0." << endl;
    	char t = 'a';
    	int c;
    
    	for (c = 0; t != '0'; c++) {
    		cin >> ptr[c];
    		if ((ptr[c] != '0') && (c == length)) {
    			ptr = arr_add(ptr, &length);
    		}
    		t = ptr[c];
    	}
    
    	arr_print(ptr, c);
    
    	delete[] ptr;
    
    	return 0;
    }
    RUN EXAMPLE:
    Code:
    Enter your name, then type 0.
    Mark DiVelbiss0
    Hello, MarkDiVelbiss
    Regardless of those 2 issues (and the type '0' cheat) the program seems to work!!!!

  4. #14
    Join Date
    Jun 2011
    Location
    Westerville, OH
    Posts
    9
    Quote Originally Posted by Edge Damodred View Post
    In Reply to Zelosh's inquiry on data structures.
    I'm copying this one into a document and saving it.
    To summarize, data structure is an abstract term for how we organize, store, and retrieve data, right?
    I don't know much about trees and what not (as in what they mean in C++, there are later videos for that) but your explanation was perfectly clear, Thank you for answering my question ^^

  5. #15
    Join Date
    Jun 2003
    Posts
    150
    Essentially you have the idea. Again with trees think of your family tree and notice where each person falls in relation to everyone else on the tree. Basically you can tell at a glance who is all descended from who.

    In games particular where you have large environments that do not fit on the screen all at once and your camera can look from any angle you possibly can use a tree structure to quickly discard huge sections of your world from needing to be drawn because those sections and their sub-sections are not even within the camera's view.

    As for linked lists I'm not saying never use them, I'm saying use them for their specific strengths and be really familiar with their concept and don't think they can only be made using pointers. In an array you could contain a linked list if each element in the array has an index number to another element in the array(trees too can be stored in this manner, makes serializing them much easier). And that's the big thing about linked lists, it a hierarchical list and that order is subject to change,

    Just don't use them where an array will do, where the order of the data doesn't have to be changed, where you're not going to be removing and inserting in the middle. Actually if order doesn't matter 'removing' from the middle is actually trivial in an array, it's just a value swap with the one on the end of the array and a decrement to the in use size of the array. That also goes for using dynamically allocated arrays too. If you know how big it needs to be at compile time you don't have to go through the trouble of using 'new' and forgetting to use 'delete []'.


    Now for the strings. '0' will not null terminate a string, as this would make the character '0' unusable in any string. Instead you need to use '\0' to null terminate a string. But this isn't your memory corruption problem. Next up is this section right here


    Code:
    	*length += 10;
    	char *ptrn = new char[*length];
    
    	for(int i = 0; i < *length; i++)
    		ptrn[i] = ptro[i];
    What's happening is your copying outside the bounds of the old array into the new array. You need to pass in the previously allocated length(what you've gotten so far from cin>> up to the point of actually calling arr_add() and then only copy up to that amount from the old array and then delete the old array. This however isn't what is causing the memory corruption either.

    The main culprit is right here.

    Code:
    	for (c = 0; t != '0'; c++) {
                    //This line here will attempt write to the character buffer one element greater than its size
                   //which will corrupt the memory, the character needs to be validated before it can be written to the array
    		cin >> ptr[c];
    		if ((ptr[c] != '0') && (c == length)) {
    			ptr = arr_add(ptr, &length);
    		}
    		t = ptr[c];
    	}
    
            //A 'more correctish' version of the loop without fixing arr_add()
    	for (c = 0; t != '0'; c++)
    	{
    		cin >> t; //Here we just grab and isolate the character to test.
    		
                    //If this is the character to end the loop, use break.
                    if(t == '0')
                    {
                            //This will break out of the the nearest loop(or switch if we were using one)
    			break; 
                    }
    		if (c == length)
    		{
    			ptr = arr_add(ptr, &length);
    		}
    		ptr[c] = t; //Only add the character to the array if we have buffer size for it and it is not the loop exit condition.
    		
    	}
    This will stop the memory corruption that happens when cin>> was writing to one space over the array. However the issue of arr_add() still remains, but it's a pretty simple fix.
    Last edited by Edge Damodred; 04-07-2012 at 12:57 AM.

  6. #16
    Join Date
    Jun 2003
    Location
    Trier, Germany
    Posts
    1,350
    Quote Originally Posted by Zelosh View Post
    From there I just made it equal NULL instead of '0' to terminate the string.
    Don't confuse the three nulls of C++:
    • 0 is for numbers, as in int i = 0;
    • '\0' is for terminating strings as in char str[42] = {'\0'};
    • nullptr is for pointers, as in void* ptr = nullptr; NULL is the old version of nullptr that was inherited from C. If your compiler supports it (Visual Studio 2010 and newer, GCC with -std=c++0x flag) you should always use nullptr instead of NULL, as the former will give a compiler error if you accidentally confuse it with one of the other nulls.


    arr_add is my function for lengthening the array by creating a new one and readjusting the old pointer. The size changes in increments of 10 rather than doubling, since I figured the numbers would get unnecessarily big by doubling, wasting space.
    One might think that, but it is not true. You waste at most 50% of the array space, which is not much (it's just a small constant factor). The main problem with constant size grow is that your array no longer has amortized constant insertion costs (for the curious: it's now O(n^2)). Imagine reading 10 GB of data that way: You would pretty much waste all your time on copying and reallocating arrays.

    PROBLEM 2: The output is great but there's no spaces. This is a minor problem, but I'm not sure how I'd get around it if I really needed to.
    cin>> eats spaces by default. Either set noskipws or use getline() instead of operator>>.

    Code:
    char t = 'a';
    int c;
    for (c = 0; t != '0'; c++) {
    	...
    	t = ptr[c];
    }
    A quick note on style: Don't mix variables in for-headers. If you get a typo, it will be impossible to spot. Instead consider using something like
    Code:
    for(char* it = ptr; it != ptr + length; ++it) {
    	char t = *it;
    or even a while loop. for can be used for very powerful things, but that doesn't always mean it should.

    As an exercise, try finding some advantages of my suggested for-loop over your for-loop. I count at least one major and three minor ones
    Last edited by ComicSansMS; 04-07-2012 at 03:46 AM.

  7. #17
    Join Date
    Jun 2011
    Location
    Westerville, OH
    Posts
    9
    To clarify, I wasn't saying '0' is null, it was just my indicator for when the string is done since it is highly unlikely anyone has a zero in their name. From there I changed the value from '0' to null manually.

    Except... looking at my code I completely forgot to do that even though I expressly intended to, so I get the confusion...

    Quote Originally Posted by Edge Damodred View Post
    What's happening is your copying outside the bounds of the old array into the new array. You need to pass in the previously allocated length(what you've gotten so far from cin>> up to the point of actually calling arr_add() and then only copy up to that amount from the old array and then delete the old array. This however isn't what is causing the memory corruption either.
    WOOPS, didn't even see that I was changing length too soon... hah... easy fix
    And I went ahead and used your suggested code with minor tweaks, since it's more orderly.

    Quote Originally Posted by ComicSansMS View Post
    Don't confuse the three nulls of C++:
    • 0 is for numbers, as in int i = 0;
    • '\0' is for terminating strings as in char str[42] = {'\0'};
    • nullptr is for pointers, as in void* ptr = nullptr; NULL is the old version of nullptr that was inherited from C. If your compiler supports it (Visual Studio 2010 and newer, GCC with -std=c++0x flag) you should always use nullptr instead of NULL, as the former will give a compiler error if you accidentally confuse it with one of the other nulls.


    One might think that, but it is not true. You waste at most 50% of the array space, which is not much (it's just a small constant factor). The main problem with constant size grow is that your array no longer has amortized constant insertion costs (for the curious: it's now O(n^2)). Imagine reading 10 GB of data that way: You would pretty much waste all your time on copying and reallocating arrays.

    cin>> eats spaces by default. Either set noskipws or use getline() instead of operator>>.
    Okay I see, so the act of constantly upgrading my array is more costly than the size itself right? I've changed it to doubling the size instead.

    Does nullptr only work with pointers then? Would I still use NULL for everything else?

    And noskipws works perfectly!! thanks!

    Code:
    for(char* it = ptr; it != ptr + length; ++it) {
    	char t = *it;
    I'll be honest my code was working a lot better before I tried to implement this. I get what it is trying to do, which is use memory arithmetic to prevent overflow as its very condition, but it doesn't seem to fit well enough into the code itself.

    I tried to rework it so that I didn't need the variable c, but it turned out to be far easier to work with c instead (at least with my current knowledge). I just got so caught up trying to do the memory arithmetic right that the program output random variables in the end. I dunno what happened, but this new code works just as well and only uses c in the for-header.

    On the other hand, I'll try to think of why your's is better than my old one.
    • Uses only one variable in the header, to prevent confusion
    • Its condition works to protect the program from overflow
    • It works directly with the memory, rather than obscure variables
    • It requires less variables, as it could replace both c and t


    Uh... I can't think of anything else atm.

    Here's the new code.

    Code:
    #include <iostream>
    
    using namespace std;
    
    char *arr_add(char *ptro, int *length) {
    	char *ptrn = new char[(*length) * 2];
    
    	for(int i = 0; i < *length; i++)
    		ptrn[i] = ptro[i];
    
    	*length *= 2;
    
    	delete[] ptro;
    	return(ptrn);
    }
    
    void arr_print(char *ptr, int length) {
    	if(ptr == nullptr) return;
    	
    	cout << "Hello, ";
    	for(int i = 0; i < length; i++)
    		cout << ptr[i];
    	cout << endl;
    }
    
    int main() {
    	int length = 10;
    	char *ptr = new char[length];
    
    	cout << "Enter your name, then type 0." << endl;
    	char t;
    
    	for (int c = 0; c != length; c++) {
    		cin >> noskipws >> t;
    
    		if(t == '0') {
    			ptr[c] = '\0';
    			arr_print(ptr, c);
    			break;
    		}
    
    		ptr[c] = t;
    
    		if (c == length-1)
    			ptr = arr_add(ptr, &length);
    	}
    
    	delete[] ptr;
    
    	return 0;
    }
    OUTPUT:
    Code:
    Enter your name, then type 0.
    Mark DiVelbiss0
    Hello, Mark DiVelbiss
    IT WORKS!
    Anything else to add?
    Last edited by Zelosh; 04-07-2012 at 01:30 PM.

  8. #18
    Join Date
    Jun 2003
    Location
    Trier, Germany
    Posts
    1,350
    Quote Originally Posted by Zelosh View Post
    Does nullptr only work with pointers then? Would I still use NULL for everything else?
    nullptr only works with pointers. NULL is on most implementations identical to the number 0, but that is not guaranteed by the standard. In particular, NULL was not intended to be used for anything else but pointers, but since it works almost everywhere as 0, people kept using it like an ordinary number. This is actually a bug in the language design: nullptr fixed NULL in that it now can only be used with pointers.

    I'll be honest my code was working a lot better before I tried to implement this. I get what it is trying to do, which is use memory arithmetic to prevent overflow as its very condition, but it doesn't seem to fit well enough into the code itself.
    That's perfectly okay, it was just a suggestion. Your current solution seems just as good.

    On the other hand, I'll try to think of why your's is better than my old one.
    You got the most important thing right: It's much more secure, since it doesn't go rampaging through your memory if the terminating \0 is missing. Your new code also makes use of this, good work!
    Here are the minor advantages I was thinking off, ordered more important first:
    My loop also limits the lifetime of both c and t to the body of the loop, where in your original version they continued to exist until the end of the function. It's generally desirable to have variables only live for as long as they are really needed.
    Your code is harder to refactor, since it poses stronger requirements to the underlying data structure than are actually needed, namely the presence of an array dereference operator (ptr[c]) rather than a simple pointer dereference (*ptr). (For the experts: yours requires a random-access iterator while the algorithm only needs a forward iterator). This is actually not easy to see, since it usually requires a fair amount of programming experience to get into this way of thinking. Just remember this: The most generic implementation (i.e. one that requires just what is needed for an efficient implementation, but no more) is usually the best.
    My code may also be more efficient on some architectures, since it uses direct derefencing instead of array-style derefencing. Emphasis on *may*. Don't use micro-optimizations like this only because you believe they might be faster (they probably won't be ). Remember what D. E. Knuth said: Premature optimization is the root of all evil.

    Here's the new code.
    Looking good. Glad you figured it out
    Last edited by ComicSansMS; 04-07-2012 at 04:50 PM.

  9. #19
    Join Date
    Jun 2011
    Location
    Westerville, OH
    Posts
    9
    Thank you guys!!! Dang, I've been here for like 2 days and I'm loving 3D Buzz.

    A special thanks for challenging me where possible without simply giving me the answer.
    I'll be relying on you all in the future as I decide to try new projects haha

    I started to get serious about programming because I want to attempt applying for an internship with Arena Net's program. It's a little out of my reach at the moment... but I'll see how far I can go.

Page 2 of 2 FirstFirst 12

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •