The "IT DOESN'T WORK!" thread

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Prelates, Moderators General

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Fri Mar 02, 2012 4:02 pm UTC

An erratum:
Jplus wrote:[...] and you could be more efficient if you moved indices from both ends of the list. Let the left index go up until it meets a value that is biggernot smaller than the pivot, let the right index go down until it meets a value that is smallernot larger, break the loop if the left index and the right index have met or swap and repeat otherwise.
(I'm going to fix this in the quoted post.)

I read the dual pivot paper, but I don't think it's faster than the normal, single-pivot method. If you partition the array into three parts you'll need to recurse less deep on average, but you make more recursive function calls. You also have to perform more index calculations and you perform two comparisons per element per partitioning pass instead of one (the paper suggests that single pivot methods need two comparisons per element too, but this is incorrect). Choosing a sensible pivot also becomes slightly harder. The author of the paper clearly didn't have a very strong background in algorithmics. At best it's going to be not much slower, but you can test how it works for you anyway.

PM 2Ring wrote:
Jplus wrote:Finally, you can improve a little by delaying the insertion sort until the end. If the subrange is shorter than your insertion sort threshold, just return directly from the quicksort function. When the topmost quicksort has returned, do a single insertion sort pass over the entire array.

Nice trick, Julian!

Thanks. It wasn't my invention though. :P
Read about introsort, the algorithm that was used in the C++ standard library. (It states that the final insertion pass doesn't make sorting faster, but that's in C++ where all function calls can be automatically inlined by the compiler.)
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby Breakfast » Fri Mar 02, 2012 5:45 pm UTC

Julian, I've handled optimizations two through four but I'm having a little trouble grasping what needs to be done for:
First of all, you're currently doing more swaps than strictly needed. There is no need to move the pivot to the end of the array, and you could be more efficient if you moved indices from both ends of the list. Let the left index go up until it meets a value that is not smaller than the pivot, let the right index go down until it meets a value that is not larger, break the loop if the left index and the right index have met or swap and repeat otherwise.
I'm sure I actually just need to take a close look at what needs to happen and I'll work it out; but could you perhaps clarify a bit. If I understand correctly, I need two indexers (left and right) that will compare the values of the items at those indices with the pivot index value. When the left index finds a value not smaller than the pivot index value and the right index finds a value not larger than the pivot index value I compare them and if the left index value is greater than the right index value I break the loop. Otherwise I swap the left and right index values and repeat the loop.

Here's the Insertion Sort so far:
Spoiler:
Code: Select all
        private static List<int> InsertionSort(List<int> listOfNumbers)
        {
            for (int i = 1; i <= listOfNumbers.Count - 1; i++)
            {
                int _insertionValue = listOfNumbers[i];

                if (listOfNumbers[0] > _insertionValue)
                {
                    int j = i - 1;

                    while (j >= 0)
                    {
                        listOfNumbers[j + 1] = listOfNumbers[j];
                        --j;
                    }

                    listOfNumbers[j + 1] = _insertionValue;
                }
                else
                {
                    int j = i - 1;

                    while (listOfNumbers[j] > _insertionValue)
                    {
                        listOfNumbers[j + 1] = listOfNumbers[j];
                        --j;
                    }

                    listOfNumbers[j + 1] = _insertionValue;
                }
            }

            return listOfNumbers;
        }

Here's the Quicksort so far:
Spoiler:
Code: Select all
        private static void QuickSort(List<int> listOfNumbers, int leftBound, int rightBound)
        {
            if (leftBound < rightBound)
            {
                int rightMinusLeft = rightBound - leftBound;

                if (rightMinusLeft <= 20)
                {
                    return;
                }
                else
                {
                    #region Quicksort

                    #region Partition Selection

                    int _partition = leftBound + (rightMinusLeft) / 2;
                    int _pivotValue = listOfNumbers[_partition];

                    int _left = listOfNumbers[leftBound];
                    int _right = listOfNumbers[rightBound];

                    if ((_pivotValue < _left && _left < _right) || (_right < _left && _left < _pivotValue))
                    {
                        _partition = leftBound;
                        _pivotValue = _left;
                    }
                    else if ((_pivotValue < _right && _right < _left) || (_left < _right && _right < _pivotValue))
                    {
                        _partition = rightBound;
                        _pivotValue = _right;
                    }

                    #endregion

                    #region Partition

                    int _temp = listOfNumbers[_partition];
                    listOfNumbers[_partition] = listOfNumbers[rightBound];
                    listOfNumbers[rightBound] = _temp;

                    int _storeIndex = leftBound;

                    for (int i = leftBound; i <= rightBound - 1; i++)
                    {
                        if (listOfNumbers[i] < _pivotValue)
                        {
                            _temp = listOfNumbers[i];
                            listOfNumbers[i] = listOfNumbers[_storeIndex];
                            listOfNumbers[_storeIndex] = _temp;

                            _storeIndex += 1;
                        }
                    }

                    _temp = listOfNumbers[_storeIndex];
                    listOfNumbers[_storeIndex] = listOfNumbers[rightBound];
                    listOfNumbers[rightBound] = _temp;

                    _partition = _storeIndex;

                    #endregion

                    QuickSort(listOfNumbers, leftBound, _partition - 1);
                    QuickSort(listOfNumbers, _partition + 1, rightBound);

                    #endregion
                }
            }
        }
I tested some more and changed the switching threshold to 20. The current average runtime is ~8 seconds.
Breakfast
 
Posts: 72
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Fri Mar 02, 2012 6:16 pm UTC

Breakfast wrote:I'm sure I actually just need to take a close look at what needs to happen and I'll work it out; but could you perhaps clarify a bit. If I understand correctly, I need two indexers (left and right) that will compare the values of the items at those indices with the pivot index value. When the left index finds a value not smaller than the pivot index value and the right index finds a value not larger than the pivot index value I compare them and if the left index value is greater than the right index value I break the loop. Otherwise I swap the left and right index values and repeat the loop.

Ok, basically what you're saying here seems to be correct but I now realise I've been a bit ambiguous in my description. Let's distinguish the index value, which represents a position in your list, from the key value at that position. Changing your words accordingly, this would be the correct interpretation:

I need two index values (left and right) that will compare the key values at the corresponding positions with the pivot (key value). When the left index points to a key value not smaller than the pivot and the right index points to a key value not larger than the pivot I compare the index values and if the left index value is greater than or equal to the right index value I break the loop. Otherwise I swap the key values pointed to by the left and right indices and repeat the loop.


Your insertion sort appears to do exactly what I suggested. Your median-of-3 pivot selection could be more efficient. Currently you're doing at least 2 and at most 8 comparisons, but you could do it in at least 2 and at most 3 comparisons. For the challenge I'll let you figure that out by yourself. :)

It's slightly disconcerting that your sort is still taking 8 seconds, I'd expect that it'd have sped up considerably by now already.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby TheVoid » Sun Mar 04, 2012 4:03 am UTC

So i am trying to learn a bit about how computers work at a very low level. ( It's fascinating :O )
And i fount a nice tutorial that explains a lot about how a boot loader works, as well as a short tutorial. Obviously, i'm jumping into a lot, but i want to try.
So this should be a simple "Hello world" boot loader.

Code: Select all
[BITS 16]
[ORG 0x7C00]

MOV AL, 65
CALL PrintCharacter
JMP $       

PrintCharacter:
MOV AH, 0x0E
MOV BH, 0x00
MOV BL, 0x07

INT 0x10
RET

TIMES 510 - ($ - $$) db 0
DW 0xAA55


It compiled fine, but i can't for the life of me figure out how to ( successfully ) put it into the boot sector of an iso. ( I am hoping to be able to use VirtualBox in order to run this.
I should mention that i'm using MAC OS X and have an ok ability with the console.
so I compile this Assembly to boot.bin, and have tried using dd in order to turn this into an ISO file.

Code: Select all
dd if=boot.bin bs=512 of=boot.iso


Again, everything worked perfectly. ( I don't see why it shouldn't, it's a direct binary copy! )
However, i'm not sure if i'm doing this right, because the VM complains that it could not use this ISO. Do i need to mount an empty ISO and do instead something like this?

Code: Select all
dd if=boot.bin bs=512 of=/dev/[mounted iso here]


in order to preserver the ISO?
How would i create an ISO file to do so if that's the problem?
thank you for your help in this. :)
User avatar
TheVoid
 
Posts: 1
Joined: Tue Dec 27, 2011 4:47 pm UTC
Location: Washington state

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Sun Mar 04, 2012 5:19 am UTC

The way bootable CDs work is quite weird... they don't actually have an MBR, or a partition table, or anything of the sort. What they actually have, is that you make a 1.44MB (that is, 1.44*1000*1024 bytes exactly) floppy-disk image, and then that gets stuffed into the ISO headers when you build the CD (look up the -b flag for genisoimage). Then when you boot from it, it loads that image as a virtual floppy drive, and then boots from that. Don't ask me why they designed it this way.

I'm not 100% certain, but I think the process is something like:
Code: Select all
dd if=/dev/zero of=boot.img bs=512 count=2880
dd if=boot.bin of=boot.img bs=512 count=1 conv=notrunc
genisoimage -b boot.img -o boot.iso somefile.txt
(the somefile.txt is because genisoimage will refuse to make a CD with no files on it)

Probably an easier way would be to just make that 1.44MB floppy disk image, and then mount it directly in vbox as a floppy disk. That way you don't need to re-gen your ISO every time you make a change to your stuff;.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby PM 2Ring » Sun Mar 04, 2012 1:26 pm UTC

phlip wrote:Don't ask me why they designed it this way.

Yeah, it's a bit weird, but I guess that design made it easier to get it to work with existing BIOS code. FWIW, there's also no-emulation mode. See El Torito (CD-ROM standard).

Your virtual machine suggestion is good, phlip, but I'd probably just use a USB stick for something like this. Of course, that requires the BIOS being able to boot off the stick. :)

While on the topic of bootloaders, I feel obliged to mention the Syslinux project. There's a lot of interesting info in the Syslinux docs.
User avatar
PM 2Ring
 
Posts: 3097
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: The "IT DOESN'T WORK!" thread

Postby Spambot5546 » Sun Mar 18, 2012 4:44 am UTC

I'm not sure if I'm a complete idiot or if it's just been too long since I worked regularly in c++, but I'm having a 2d array problem.

The following is an initialization function from a neural net AI I'm developing.
Code: Select all
void WeightedNet::setup(char* configFile)
{
    ifstream in;
    in.open(configFile);
    int numLayers;
    if (in.is_open())
    {
        in >> numLayers;
        layers = numLayers;
        layerSizes = new int[numLayers];
        allNodes = new WeightedNode*[numLayers];
        int nodesThisLayer, connsThisLayer;
        for (int cntr = numLayers-1; cntr >=0; cntr--)
        {
            in >> nodesThisLayer >> connsThisLayer;
            layerSizes[cntr] = nodesThisLayer;
            allNodes[cntr] = new WeightedNode[nodesThisLayer];
            for (int ndx = 0; ndx < nodesThisLayer; ndx++)
            {
                WeightedNode blank;
                allNodes[cntr][ndx] = blank;
            }
           
            for (int ndx = 0; ndx < connsThisLayer; ndx++)
            {
                if (cntr < numLayers-1)
                {
                    int thisNode, connNode;
                    float connWeight;
                    in >> thisNode >> connNode >> connWeight;
                   
                    allNodes[cntr][thisNode].addConn(allNodes[cntr+1][connNode], connWeight);
                    allNodes[cntr][thisNode].layer = cntr;
                    allNodes[cntr][thisNode].index = thisNode;
                }
                else
                {
                    allNodes[cntr][ndx].layer = numLayers - 1;
                    allNodes[cntr][ndx].index = ndx;
                }
            }
        }
        outSize = layerSizes[layers-1];
    }
    in.close();
}


Execution halts on the line
Code: Select all
            allNodes[cntr] = new WeightedNode[nodesThisLayer];

and I can't figure out why. The only error I get is
Code: Select all
Signal received: SIGSEGV (?) with sigcode ? (?)
From process: ?
For program neural_nets, pid -1

You may discard the signal or forward it and you may continue or pause the process
To control which signals are caught or ignored use Debug->Dbx Configure

Which isn't telling me anything.

Oh, and the weird thing is that in checking whether the constructor on the node was being called I found out that it is, in fact, being called 16172 times*. I have no idea what would cause that, "nodesThisLayer" has a value of 1 at this point. Thoughts?

*You're probably thinking the same thing I was, but no, 16172 is not a power of 2. 2^14 is 16384.
"It is bitter – bitter", he answered,
"But I like it
Because it is bitter,
And because it is my heart."
Spambot5546
 
Posts: 1350
Joined: Thu Apr 29, 2010 7:34 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Sun Mar 18, 2012 10:34 am UTC

I don't see any obvious error (yet), but I do have a question that might help us clarify. What is the value of numLayers?
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby Spambot5546 » Sun Mar 18, 2012 1:10 pm UTC

At that point in execution

numLayers=4
nodesThisLayer=1
connsThisLayer=1
"It is bitter – bitter", he answered,
"But I like it
Because it is bitter,
And because it is my heart."
Spambot5546
 
Posts: 1350
Joined: Thu Apr 29, 2010 7:34 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby jaap » Sun Mar 18, 2012 1:59 pm UTC

I've snipped most lines:
Spambot5546 wrote:
Code: Select all
            allNodes[cntr] = new WeightedNode[nodesThisLayer];
            ...
            for (int ndx = 0; ndx < connsThisLayer; ndx++)
            {
                    ...
                    in >> thisNode >> connNode >> connWeight;
                    allNodes[cntr][thisNode].addConn(allNodes[cntr+1][connNode], connWeight);
                    ...
                    allNodes[cntr][ndx].layer = numLayers - 1;
                    allNodes[cntr][ndx].index = ndx;
            }


Are you sure that ndx < nodesThisLayer? Or rather that connsThisLayer < nodesThisLayer?
Are you sure that thisNode < nodesThisLayer?
Given that you are reading some numbers from a file, you really must put some sanity checks in so that you see immediately when things start to wrong. An extra space in the file causes all the numbers to go out of sync with your program.

I think that you are probably overwriting memory at some iteration of the loop, and that it only crashes at a later iteration.
User avatar
jaap
 
Posts: 1789
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby Spambot5546 » Sun Mar 18, 2012 2:57 pm UTC

I thought that, too, but if I throw in some debug lines thusly

Code: Select all
void WeightedNet::setup(char* configFile)
{
    cout << "In fx" << endl;
    ifstream in;
    in.open(configFile);
    int numLayers;
    if (in.is_open())
    {
        cout << "is open" << endl;
        in >> numLayers;
        layers = numLayers;
        layerSizes = new int[numLayers];
        allNodes = new WeightedNode*[numLayers];
        int nodesThisLayer, connsThisLayer;
        for (int cntr = numLayers-1; cntr >=0; cntr--)
        {
            cout << "loop1" << endl;
            in >> nodesThisLayer >> connsThisLayer;
            layerSizes[cntr] = nodesThisLayer;
            allNodes[cntr] = new WeightedNode[nodesThisLayer];
            for (int ndx = 0; ndx < nodesThisLayer; ndx++)
            {
                cout << "loop2" << endl;
                WeightedNode blank;
                allNodes[cntr][ndx] = blank;
            }
           
            for (int ndx = 0; ndx < connsThisLayer; ndx++)
            {
                cout << "loop3" << endl;
                if (cntr < numLayers-1)
                {
                    int thisNode, connNode;
                    float connWeight;
                    in >> thisNode >> connNode >> connWeight;
                   
                    allNodes[cntr][thisNode].addConn(allNodes[cntr+1][connNode], connWeight);
                    allNodes[cntr][thisNode].layer = cntr;
                    allNodes[cntr][thisNode].index = thisNode;
                }
                else
                {
                    allNodes[cntr][ndx].layer = numLayers - 1;
                    allNodes[cntr][ndx].index = ndx;
                }
            }
        }
        outSize = layerSizes[layers-1];
    }
    in.close();
}


Then I get the output
Code: Select all
In fx
is open
loop1

RUN SUCCESSFUL (total time: 166ms)

Which both shows that it fails on the first execution but also begs the question "Why the tits does it say 'RUN SUCCESSFUL'!?" It so very clearly wasn't.

Edit: Running it on my school's dev server (no, this isn't homework) which uses g++ in linux, it says "Segmentation fault (core dumped)" instead of "RUN SUCCESSFUL (total time: 166ms)".

Edit2: Also, on the school's server it executes the constructor for WeightedNode 130,945 times, compared to the 16,172 times in Cygwin. This is seriously bizarre.

Edit3: Guess who has two thumbs and is a moron. This guy! In trying to figure out why the constructor was being called so many times I took a look in the constructor and realized that I was initializing each nodes connections (which are also WeightedNode objects) resulting in infinite recursion and a segfault. Since I was doing that for literally no reason I just took those out and it executes more-or-less correctly. Still some debugging to do, but one mystery solved.
"It is bitter – bitter", he answered,
"But I like it
Because it is bitter,
And because it is my heart."
Spambot5546
 
Posts: 1350
Joined: Thu Apr 29, 2010 7:34 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Mon Mar 19, 2012 10:27 am UTC

Just for the record: when jaap said "insert some sanity checks" I don't think he meant "insert statements that report the point of execution". Rather, he meant "insert assertions to verify that your assumptions are correct". To go with the code that jaap quoted:
Code: Select all
            assert(connsThisLayer < nodesThisLayer);
            allNodes[cntr] = new WeightedNode[nodesThisLayer];
            ...
            for (int ndx = 0; ndx < connsThisLayer; ndx++)
            {
                    ...
                    in >> thisNode >> connNode >> connWeight;
                    assert(thisNode < nodesThisLayer);
                    allNodes[cntr][thisNode].addConn(allNodes[cntr+1][connNode], connWeight);
                    ...
                    allNodes[cntr][ndx].layer = numLayers - 1;
                    allNodes[cntr][ndx].index = ndx;
            }


Since the error wasn't in this part of your code it doesn't really matter anymore, but it's good to remember that inserting assertions into your code is generally a good idea. They help you to quickly identify errors in your assumptions and you can easily disable them at compilation with the option -DNDEBUG. All you need to do in order to use them is to #include <cassert>.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby Bharrata » Fri Mar 23, 2012 2:59 am UTC

This isn't so much a "doesn't work" problem as a "where/how to begin" problem, but I don't think it warrants a new thread.

I'm using C++ for the first time for a school project emulating the different types of memory paging algorithms in such a way that it evaluates their effectiveness (page fault rates) and I want the number of available pages in "virtual" memory and the sequence of pages to be used/loaded to be input from the user.

I'm going to be writing it in the Visual Studio IDE; the problem I'm having is that I've only used VS for BASIC and when doing so there's usually a default UI form to work with....there isn't with C++ and I'm unsure if it's expected that I code the UI myself (or if I should for that matter) or if there's something I'm completely missing because it's my first time working with C++.


The interface doesn't need to be pretty or complex, I just need an easy way to prompt the user for their specifications, basically a label and a textbox.


For what it's worth, I know this would be simple in Python, but my professor suggested using C++ so that I could use stacks (she feels like that's the simplest way to get the algorithms to work) and I've wanted to start learning the C-family of languages for awhile anyways.
Bharrata
 
Posts: 233
Joined: Sun May 15, 2011 7:57 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Spambot5546 » Fri Mar 23, 2012 3:07 am UTC

You're looking for a GUI, but one isn't necessary for this. Just make a basic console application and use cin to prompt the user for input.

There ARE ways in Visual Studio to make windowed programs for C++. I think they even do WYSIWYG development. But unless a GUI is one of your requirements, don't waste your time.
"It is bitter – bitter", he answered,
"But I like it
Because it is bitter,
And because it is my heart."
Spambot5546
 
Posts: 1350
Joined: Thu Apr 29, 2010 7:34 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Bharrata » Fri Mar 23, 2012 3:12 am UTC

I just came back to say I figured out how to make a window (and that I need to be a little more patient in the future about looking and trying things) but thank you, you probably just saved me a bunch of time.


edit: ....command line prompts always make me feel like i'm 6 years old again, in a very good way 8) ty again!
Bharrata
 
Posts: 233
Joined: Sun May 15, 2011 7:57 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Bharrata » Thu Apr 05, 2012 3:24 am UTC

Quick question:

When creating a dynamic memory array (not sure if it's specifically called a heap or not) in C++, if no values have been placed within the array are the blocks of memory considered to be holding null values, or something else?

The slice of code in question:

Code: Select all
int virtualmem;
char pagename;
char * p;
p = new (nothrow) char [virtualmem];


So will p[0] = '\0' ?
Bharrata
 
Posts: 233
Joined: Sun May 15, 2011 7:57 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Thu Apr 05, 2012 3:50 am UTC

No - if you create an object or an array of a non-trivial class, it'll be initialised, but if it's just of a basic data type, then it'll be uninitialised (so it'll contain whatever that patch of memory contained before)...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby Bharrata » Thu Apr 05, 2012 4:01 am UTC

phlip wrote:No - if you create an object or an array of a non-trivial class, it'll be initialised, but if it's just of a basic data type, then it'll be uninitialised (so it'll contain whatever that patch of memory contained before)...


Can I assume, at least when int virtualmem <=10 (or something comparatively small), that the system will be using free memory to create the new array?

More specific to the problem I'm foreseeing for my program is that I need a way to distinguish between the initial value of p[for any k <= virtualmem] and the same block of memory once it has a value stored within it. It might be impossible to know the initial value, but it's my first time coding in C++ so I'm not very knowledgeable about alternate ways to do what I want.

Basically, the very end of this piece is what I'm trying to figure out:

Code: Select all
for (k = 0; k < virtualmem; k++)
      if (pagename != p[k]; p[k] != // no idea what to put here as I don't know what the initial value will be )
Bharrata
 
Posts: 233
Joined: Sun May 15, 2011 7:57 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby Xanthir » Thu Apr 05, 2012 4:21 am UTC

You have to track that yourself. This is typically done either with wrapping all your stores in a light data structure (when implemented for real, this is sometimes done by reserving a few bits for tagging purposes, for example) so you can definitely tell the difference between "initial" and "holds a value", or by maintaining a parallel data store that tracks whether the main store has been written to or not in each index.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
User avatar
Xanthir
My HERO!!!
 
Posts: 4225
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Thu Apr 05, 2012 4:28 am UTC

Bharrata wrote:Can I assume, at least when int virtualmem <=10 (or something comparatively small), that the system will be using free memory to create the new array?

I'm not sure what you mean by "free memory"... if you mean "memory that's not currently in use", then yes, it'll always be put in free memory, it'd be a poor allocator that let things overlap... if you mean "memory that's ever been used", then no, you can't assume that. But even if it was placed in brand new memory that's never been used since the computer was turned on, that still doesn't guarantee that it'd be filled with all-zeros.

Bharrata wrote:More specific to the problem I'm foreseeing for my program is that I need a way to distinguish between the initial value of p[for any k <= virtualmem] and the same block of memory once it has a value stored within it. It might be impossible to know the initial value, but it's my first time coding in C++ so I'm not very knowledgeable about alternate ways to do what I want.

Well, the usual way to make sure it's initialised is to just initialise it yourself after you create it:
Code: Select all
char *p = new char[virtualmem];
for (int i = 0; i < virtualmem; i++)
  p[i] = '\0';

Of course, this only works for your purpose if there's some value that you're never going to want to store in the array, that you can recognise as an "unused" value. If you could potentially want to store the entire range of values in there, then the usual trick is to have a separate value to store the state of the variable:
Code: Select all
char *p = new char[virtualmem];
bool p_filled = false;
(If you need a separate "is filled" flag for each value in the array, you could make an array of such flags). As Xanthir suggested, if you're at all familiar with the classes and objects side of C++, you could wrap the value and is-filled flag together into a single class, and then have just an array (or, preferably, a vector/list/etc) of those.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby Bharrata » Thu Apr 05, 2012 5:46 am UTC

phlip wrote:
Bharrata wrote:More specific to the problem I'm foreseeing for my program is that I need a way to distinguish between the initial value of p[for any k <= virtualmem] and the same block of memory once it has a value stored within it. It might be impossible to know the initial value, but it's my first time coding in C++ so I'm not very knowledgeable about alternate ways to do what I want.

Well, the usual way to make sure it's initialised is to just initialise it yourself after you create it:
Code: Select all
char *p = new char[virtualmem];
for (int i = 0; i < virtualmem; i++)
  p[i] = '\0';


Forehead slapping-ly simple solution :lol:

Of course, this only works for your purpose if there's some value that you're never going to want to store in the array, that you can recognise as an "unused" value.


It needs to recognize both "free" and "used but different value than the value being compared to it" so it works perfectly.

(If you need a separate "is filled" flag for each value in the array, you could make an array of such flags). As Xanthir suggested, if you're at all familiar with the classes and objects side of C++, you could wrap the value and is-filled flag together into a single class, and then have just an array (or, preferably, a vector/list/etc) of those.


Honestly, that was an idea I had initially for this project (in the pseudo-code) but for now I'm just going to use a separate counter variable to ++ each time the conditions for a value change are met, as again, this is my first foray into C-languages and I'm trying to take it step by step.


I'd assume a <char, bool> tuple might be what you're describing?

For how the project is structured it would work better as a "was used" flag rather than an "is filled". The char p[virtualmem] is smaller than the list being placed into it. As in, the pagename values come from an istream file which, for the sake of clarity, has "a b c d e f g" as individual characters on separate lines, which then line by line get compared with and possibly placed in p[virtualmem] which may only have 3 index positions but is initially n-sized. (So if pagename was an array instead of istream input it would be easy to flag the occurrence of the value use.) The number of occurrences of values being placed in p[virtualmem] is divided by the total number of pagename values to find the efficiency.


Not very exciting, I know, but having taken only one programming course so far it gets me excited. It will be more interesting if I can modify it from a pseudo-FIFO policy to a LRU policy.


Anyway, thank you muchly Xanthir and phlip, at the very least you've saved me the hassle of tracking down my professor tomorrow and educated me a bit more about the nuances of true OOP.
Bharrata
 
Posts: 233
Joined: Sun May 15, 2011 7:57 pm UTC

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Thu Apr 05, 2012 6:26 am UTC

Well, none of this is OOP so far... it's still just variables and stuff interacting with it. OOP would be wrapping this all into an object... something like:
Code: Select all
class FlaggedChar
{
  bool set;
  char value;
public:
  FlaggedBool() : set(false) {}
  FlaggedBool(char v) : set(true), value(v) {}
  char getValue()
  {
    if (!set)
      return '\0'; // alternatively: throw an exception
    return value;
  }
  void setValue(char v)
  {
    value = v;
    set = true;
  }
  bool isSet()
  {
    return set;
  }
  void clear()
  {
    set = false;
  }
};
(In a more-real C++ snippet, you'd want a bunch more code in here to handle other fanciness, like operator overloading and copy-constructors and templating and such... leaving those out here to just be a simple example for someone new to the language.)

Then you'd be able to just go:
Code: Select all
FlaggedChar *p = new FlaggedChar[10]; // or, better, vector<FlaggedChar> p(10);
if (p[0].isSet())
{
  // This won't happen
}
p[0].setValue('A');
if (p[0].isSet())
{
  // This will happen
}
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Thu Apr 05, 2012 10:02 am UTC

I think OOP would be overkill in this case, though.

Unrelated, I'd like to show some variants of this snippet.
phlip wrote:
Code: Select all
char *p = new char[virtualmem];
for (int i = 0; i < virtualmem; i++)
  p[i] = '\0';

Using modern C++:
Code: Select all
#include <vector>
typedef std::vector<char> vec_char;

// ...

vec_char p(virtualmem, '\0');

Using oldschool C:
Code: Select all
#include <stdlib.h>

// ...

char *p = (char*) calloc(virtualmem, sizeof(char));

Using oldschool C style in C++:
Code: Select all
#include <cstdlib>

// ...

char *p = static_cast<char*>(std::calloc(virtualmem, sizeof(char)));
Last edited by Jplus on Tue Apr 10, 2012 11:12 am UTC, edited 1 time in total.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Tue Apr 10, 2012 1:40 am UTC

(Technically, old-school C would be using malloc, not new[], so you'd just call calloc and be done with it...)
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Tue Apr 10, 2012 11:06 am UTC

phlip wrote:(Technically, old-school C would be using malloc, not new[], so you'd just call calloc and be done with it...)

Oops, right. I'll edit my post.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby Yakk » Tue Apr 10, 2012 11:37 am UTC

++C style (using C++ features to modify/make C code cleaner)
Code: Select all
template<typename T>
T* calloc( size_t count = 1 )
{
  return static_cast<T*>(calloc( count, sizeof(T) ) );
}

struct OnExit
{
  std::function< void() > doThis;
  static void doNothing() {}
  OnExit():doThis(doNothing) {}
  OnExit( std::function< void() > const& doThis_ ): doThis(doThis_) {}
};

void abort( OnExit& onExit )
{
  onExit.doThis = OnExit::doNothing;
}

// ...

char *p = calloc<char>( virtualmem );
OnExit cleanup_p( [p]{ if(p) free(p); } );

// ...
abort(cleanup_p);
return p;

including a RAII based replacement for the "goto OnExit" C pattern.

(This is what I sometimes do when I'm working on old style C code in a C++ compiler, and I don't want to do serious refactoring.)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The "IT DOESN'T WORK!" thread

Postby Shivahn » Fri Apr 13, 2012 1:02 am UTC

I'm using Python to automate as much of my work as possible. I wrote a program that takes a bunch of word files and moves them to another spot, and I'm trying to add in functionality to print every file that's been moved. I looked into it, and the best way to do this appears to be by making an os.system() call.

So here's my trouble: Python's not passing everything I want it to to the command line. The call is like this:

Code: Select all
os.system('"C:\\Program Files\\Someotherstuff\\Winword.exe "+"C:\\Someotherdirectory\\somedirectory\\file.doc "+"switches for word to make it print how I want"')


That runs find when I put it directly into the CLI. However, when I make the os.system() call from Python, it quits faster than I can read it with error code 1. By adding '|| ping 1.1.1.1' to the end, I slowed it down to see what the command line itself was saying, and it's "'C:\Program' is not recognized as an internal or external command, operable program or batch file."

So, it looks to me like what's happening is that Python is not escaping the first double quote for some reason, passing the literal 'C:\Program Files' to the CLI instead of what I want it to pass, which is '"C:\Program Files', so Windows is trying to execute C:\Program instead of the entire path given. I can't figure out how to get it to pass what I want, though. What's going on?
User avatar
Shivahn
 
Posts: 2177
Joined: Tue Jan 06, 2009 6:17 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby phlip » Fri Apr 13, 2012 1:30 am UTC

system() is clunky, especially on Windows with its never-reliable shell-quoting system. Stackoverflow says: use subprocess.call instead, as that takes the command-line parameters as separate arguments instead of one long command string.

Another alternative is to use os.startfile(filename, "print"), and let shell32 do all the work of looking everything up and calling Word appropriately. This should behave identically to right-clicking the file in Explorer and choosing "Print".
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7091
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: The "IT DOESN'T WORK!" thread

Postby Shivahn » Fri Apr 13, 2012 1:54 am UTC

Oh, heh. My Google Fu is weak.

Thanks a bunch, phlip! I'll try those out tomorrow.
User avatar
Shivahn
 
Posts: 2177
Joined: Tue Jan 06, 2009 6:17 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby EvanED » Fri Apr 13, 2012 4:53 pm UTC

Ahhhh why is the [] operator on STL maps sooooo stupid. I really appreciate how you can't use it on a const map. That's nice.

(Sorry, that is all. We return you to your regularly-scheduled broadcast. Also, I know why it is that way, and the choice was somewhat reasonable, but still... it's obnoxious. Actually I guess I don't like the behavior of the [] operators in any STL class. :-p)
EvanED
 
Posts: 4038
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: The "IT DOESN'T WORK!" thread

Postby Shivahn » Fri Apr 13, 2012 9:56 pm UTC

This:
phlip wrote:Another alternative is to use os.startfile(filename, "print"), and let shell32 do all the work of looking everything up and calling Word appropriately. This should behave identically to right-clicking the file in Explorer and choosing "Print".

worked nicely. I'll toy around with subprocess if I ever need to twerk the program, but since the os module was already imported (and I am supremely lazy) this was an excellent fix.
User avatar
Shivahn
 
Posts: 2177
Joined: Tue Jan 06, 2009 6:17 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby Yakk » Sat Apr 14, 2012 10:29 am UTC

[quote="EvanED"]Ahhhh why is the [] operator on STL maps sooooo stupid. I really appreciate how you can't use it on a const map. That's nice.[\quote]Hmm? If you want to find only, find()!=end() idiom works.

You do not like auto creation eh?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The "IT DOESN'T WORK!" thread

Postby EvanED » Sat Apr 14, 2012 6:15 pm UTC

Yakk wrote:
EvanED wrote:Ahhhh why is the [] operator on STL maps sooooo stupid. I really appreciate how you can't use it on a const map. That's nice.[\quote]Hmm? If you want to find only, find()!=end() idiom works.

You do not like auto creation eh?

No.

As far as I'm concerned, op[] is the easiest thing to use and should have the most desirable semantics. In the case of vector, I strongly feel this means it should do bounds checking. (And at() -- or even better, some unsafeAt() function -- should not.) If you're not doing bounds checking, it seems to me like half the benefit of vectors over raw arrays has evaporated. And so the present design makes everyone choose between the better syntax (v[x]) which people are used to and essentially every other programming language uses, and better semantics (v.at(x)).

Now, in the case of map, consider an alternative design where there was no auto-insertion, and it instead threw an assertion. Under this design, if you did want auto-insertion, you'd have to call some function. m[x] turns into m.setdefault(x) or something (using Python's name). But under the current API, what do I have to do if I want that behavior? I need something like
Code: Select all
map<blah>::const_iterator iter = mymap.find(item);
if (iter == mymap.end()) {
    throw Something();
}

then use iter->second. So one expression has exploded into multiple statements. Do you know how many times I've written a little helper function that does that so I can use the damn thing in an expression? Now, in part this isn't really the fault of [], it's the fault of the fact that the standards committee didn't add what you might say is the map equivalent of vector's at(). It'd be perfectly possible to envision such a function being present, and it would at least go a long way to alleviating my complaint, though what I said above about using worse syntax for the more natural operation still applies.

And this may be a symptom of the "vocal minority", but I sort of feel like I do more manipulations of const maps than I do of non-const maps.

Also, auto-insertion has another problem, which is that you can't use map's [] with a type that doesn't have a default constructor. This is also obnoxious.
EvanED
 
Posts: 4038
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: The "IT DOESN'T WORK!" thread

Postby Jplus » Sat Apr 14, 2012 7:43 pm UTC

I think you and I have different tastes (for example, I don't think vector::at has "better" semantics than vector::operator[]). I imagine that to your taste, C++ is not a very nice language.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1427
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: The "IT DOESN'T WORK!" thread

Postby EvanED » Sat Apr 14, 2012 7:54 pm UTC

Jplus wrote:I think you and I have different tastes (for example, I don't think vector::at has "better" semantics than vector::operator[]). I imagine that to your taste, C++ is not a very nice language.

To a large extent that's true, to be honest. :-) It provides too few guarantees and it provides too few operations for which there are guaranteed-safe ways to do it (we had that discussion a while ago about iterators, in particular). I subscribe to the philosophy that says that you should write your program in a safe language, and then only rewrite the bottlenecks to cut corners like bounds checking. C++ makes it too hard to do that.

I'd much rather be using something else, but circumstances force my hand. :-) I've said a few times I think basically no one should be using C any more, and that only applies slightly less to C++. In the long run, I think it's unsustainable.
EvanED
 
Posts: 4038
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: The "IT DOESN'T WORK!" thread

Postby Yakk » Sun Apr 15, 2012 4:58 pm UTC

I hope you don't mind that I fixed yoru quote-chain. :)
EvanED wrote:
Yakk wrote:
EvanED wrote:Ahhhh why is the [] operator on STL maps sooooo stupid. I really appreciate how you can't use it on a const map. That's nice.[\quote]Hmm? If you want to find only, find()!=end() idiom works.
You do not like auto creation eh?

No.

As far as I'm concerned, op[] is the easiest thing to use and should have the most desirable semantics.
In C++, the decision was that the std library "most desirable semantics" would be "as fast as a hand-written C implementation, with as much free safety as you can pull off given that restriction".

They did mess up, in that range based iteration would have been as fast (or faster! It could easily be easier for a compiler to optimize) and much safer than iterator based iteration.

Throwing, for example, requires a non-trivial amount of overhead (even the existence of throwing in your compilation unit!), to the extent that many people compile C++ without throwing enabled to reduce that overhead. new returning nullptr instead of throwing on failure, for example, is a pretty common modification to new's syntax.

This is one of the reasons why my favorite parts of C++ are the static safety. This offloads the "cost" of safety to compile time, where you aren't running on a (say) battery-operated smartphone, where every operation reduces the device's charge.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The "IT DOESN'T WORK!" thread

Postby gametaku » Mon Apr 23, 2012 11:46 am UTC

So I have the following code to multiply to Matrices which gives me a 1.000000000 on the 0,5 index and 1, 6 index of the result matrix.

Code: Select all
   Matrix<T> operator*(Matrix<T> rhs){
         Matrix<T> results(rows, rhs.cols);
         int len = results.cols * results.rows;
         int matrixBIndex = 0;

         for(int index = 0; index < len; index++)
         {
            
            int curRow = index / rhs.cols;
            int curCol = index % rows;
            int matrixAIndex = curRow * cols;

            T sum = T();
            for(int i = 0; i < rhs.rows; i++)
            {
               int mA = matrixAIndex + i;
               int mB = matrixBIndex +  (i * rhs.cols);
               double valueA = items[mA];
               double valueB = rhs.items[mB];
               double value = valueA * valueB;
               sum += items[mA] * rhs.items[mB];
            }
            results.items[index] = sum;


            matrixBIndex++;
            matrixBIndex = (matrixBIndex == rhs.cols) ? 0 : matrixBIndex;
         }
         return results;
      }


and when I multiply

Code: Select all
1.0142399285975089e-005,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000

0.00000000000000000,4.3439589002097432e-009,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000

0.00000000000000000,0.00000000000000000,3.8573610749470116e-009,0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000

0.00000000000000000,0.00000000000000000,0.00000000000000000,8.3918637859524227e-008,0.00000000000000000,0.00000000000000000,0.00000000000000000

0.00000000000000000,0.00000000000000000,0.00000000000000000,0.00000000000000000,1.0217100877702606e-007,0.00000000000000000,0.00000000000000000

0.00000000000000000,0.00000000000000000,-9.8422106304504669e-005,0.00000000000000000,0.00000000000000000,0.0057696575348317692,0.00000000000000000

0.00000000000000000,0.00000000000000000,0.00000000000000000,-7.2137627378349227e-005,0.00000000000000000,0.00000000000000000,0.0069817491263137865



0.00000000000000000,0.00000000000000000
0.00000000000000000,0.00000000000000000
0.00000000000000000,0.00000000000000000
0.00000000000000000,0.00000000000000000
0.00000000000000000,0.00000000000000000
173.32051234634636,0.00000000000000000
0.00000000000000000,143.23058332632735
gametaku
 
Posts: 149
Joined: Tue Dec 30, 2008 2:21 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby jaap » Mon Apr 23, 2012 1:10 pm UTC

gametaku wrote:So I have the following code to multiply to Matrices which gives me a 1.000000000 on the 0,5 index and 1, 6 index of the result matrix.


You haven't said what answer you expected. Looking at the matrices, I would think that is the right answer:

0,5:
The only non-zero term is 0.0057696575348317692 * 173.32051234634636 == 1.0000

1,6:
The only non-zero term is 0.0069817491263137865 * 143.23058332632735 == 1.0000
User avatar
jaap
 
Posts: 1789
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby Роберт » Wed May 23, 2012 3:35 pm UTC

Freakin' namespaces...

EDIT: aha! I found it. Why the heck did the person put this function declaration out of the namespace?
The Great Hippo wrote:[T]he way we treat suspected terrorists genuinely terrifies me.
Роберт
 
Posts: 4300
Joined: Wed May 14, 2008 1:56 am UTC

Re: The "IT DOESN'T WORK!" thread

Postby Shivahn » Thu May 24, 2012 6:19 pm UTC

Ugh, I am having serious trouble with polymorphism in C++.

So I have a base class, Component, which is the base of all the components in my system. Every actual component I use is a specialized subclass, so I can define their behavior entirely separately. In this case, I'm doing collision detection and then trying to pass a message consisting of an enumerated value and an int value from the collider to the collidee. It'd be ideal if the collidee was polymorphic, as I don't necessarily want everything to react the same to a collision.

Anyway. Component has a virtual function, virtual void receive(int, int) {};. The derived component, Collide, has an switch implemented in its member void receive(colmnessage message, int value).

So I iterate over a list of component pointers, using a std::list<Component*>::iterator it, and if I detect a collision between a collider and the thing being pointed at by the pointer pointed at by it, then I call receive (specifically, I call (*it)->receive(collider->getMessage(), collider->getValue())). This calls the Component version of receive. I can get it to work by downcasting using dynamic_cast, but I feel like I don't know quite what's going on, and I don't understand why it doesn't work (I thought that since it's a virtual function, it'd check the subclass for the receive function first). Can someone tell me what is happening?
User avatar
Shivahn
 
Posts: 2177
Joined: Tue Jan 06, 2009 6:17 am UTC

PreviousNext

Return to Coding

Who is online

Users browsing this forum: No registered users and 11 guests