• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Programming |OT| C is better than C++! No, C++ is better than C

K

Koren

Member
close to the edge said:
What database are you using?
Click to expand...
I'm open to suggestions... Not sure if I'll access it with PHP or Python yet (probably the former). I was leaning towards MariaDB since I've already used this, but one of my friends is using PostgreSQL a lot, and says I should switch each time, it may be a good opportunity.

close to the edge said:
For instance, with PostgreSQL there's also the possibility of storing the keywords/tags as a string array (VARCHAR[]) on the document table directly.
Click to expand...
And use IN keyboard? Or something else? Thanks, will look into this...

Edit: scratch that... Just found the @>. That's handy!

You may have done in 5 minutes what my friend haven't been able to do in 5 years ;)

close to the edge said:
I read a performance comparison (for PostgreSQL) not too long ago because I had the same problem: http://www.databasesoup.com/2015/01/tag-all-things.html
Click to expand...
That's *exactly* what I was looking for... No doubt, this thread delivers, as usual ;) A huge thank.

Though I wonder... The "Id" solution seems to be slow because he's doing a join... I probably would have used a select to get the IDs of keyword, then used the IDs in searchs, not doing a join. I expected this:
- to be faster than the "Text" approach, because comparing integers should be slightly faster than comparing chains (although barely)
- to be more compact than the "Text" approach, but this shows clearly it's not the case

So at least, I've already learned something, even not taking into account the more advanced strategies. Great read...
 
JeTmAn81

JeTmAn81

Member
I've been brushing up on C++ lately. In my day job and side projects I never have need for it (garbo-collected langs only), so what would be a good use case project to try out some C++? Anyone? Bueller?
 
D

Deuce Deuce

Member
JeTmAn81 said:
I've been brushing up on C++ lately. In my day job and side projects I never have need for it (garbo-collected langs only), so what would be a good use case project to try out some C++? Anyone? Bueller?
Click to expand...

Something where you need tight speed/memory optimizations?

You might take one of your projects in the gc'ed languages and see if you can make it faster in C++ or something.
 
JeTmAn81

JeTmAn81

Member
Deuce Deuce said:
Make a game that doesn't have garbage collection hitches like Unity does :p
Click to expand...

My game is just a simple Tetris ripoff so it's NBD. The shortcuts of developing in Unity are definitely worth it.

Edit: Another issue. I've got a .NET webform builder I've been working on for several years. It can build complex forms and supply a variety of maintenance features very easily. I've thought of open sourcing it but I'm not sure what the potential audience might be.

It seems like there's no free great unlimited solution for this out there. It would be tons more with if I did get people to start using it. How do I know if it's worth it?
 
C

cpp_is_king

Member
I've been thinking about trying to write a custom loader. Not necessarily for any practical purpose, but just because I think it would be an interesting exercise into understanding the depths of executable and object file formats.

Like right now you run foo.exe and you get a process called foo.exe, but i want write load.exe and you call it as "load.exe c:\foo.exe", and in process explorer you see load.exe, but foo.exe is running inside of it and the program behaves identically to as if you had run foo.exe itself.

From there you can do all kinds of neat stuff like ASLR, encrypting the code in memory, and a bunch of other stuff. If you wanted to get really bizarre, you coudl even write an ELF loader for Windows (or a COFF loader for Linux), and then hack up the source code for an existing linker like LLD, gold, etc to output the opposite file format and try to run it.
 
cheezcake

cheezcake

Member
Eridani said:
Neural networks aren't really some black box that we don't understand though. The math behind them is actually not all that complicated, and not all that different from other machine learning approaches. It can't be called a black box when we understand exactly how it works. We're also using our knowledge of how they work to constantly improve deep learning approaches, and to use them in combination with other things to achieve amazing results.

It's true that the output returned by neural networks isn't easy to understand, but that's by design really. You mentioned object recognition specifically, so let's look at that - or more generally, image classification. One of the most basic strategies that can be used to solve this problem is to manually come up with simple filters that describe your classes well and using them to classify images. It's an approach that is used quite a bit in several fields. With convolutional neural networks you're just taking out the manual part and using an error optimization function to automatically create filters that you know will work well in separating your classes. I don't see what's sad about that - it's obviously impossible to manually come up with filters that could classify every type of image (or recognize every type of object), and we're never going to find some underlying math behind that either (and if we are, deep learning is one of the better ways we have of doing that).

I also don't know why you're under the impression people aren't trying to understand results returned by deep neural networks. Here's a paper about visualizing convolutional neural networks to better understand the results they come up with. It is currently cited by 2035 other papers, which is quite a significant number.

The amount of research going into deep learning right now is also pretty staggering, mostly because just throwing some data into a neural network is very often not going to be enough.
Click to expand...

I never claimed we don't understand how a neural network fundamentally works, of course we do. The issue is we can't decipher what a trained kernel is actually doing from a conceptual point of view. It's also not really by design, that implies it's intentional we don't want to gather that understanding, it's more of an unintentional consequence.

Your also asserting that the deep learning algorithm in image classification is just using the same classical feature-based algorithms we used to use and the difference is that it just generates the feature classes automatically vs someone manually doing it. That's fundamentally unknown. The point of the deep learning algorithm is it requires absolutely no knowledge of the type of data it's going to be trained with, we don't know what algorithm it's using, whether it's effectively an extension of featured based classification, a significant modification to it, or something different.

I also didn't really say no one was working on it, I mean people are going to, the issue is whether we can decipher the fundamental truths that a trained kernel is operating on and whether we can do it at a pace in which we aren't permanently chasing a target moving faster than us.
 
phisheep

phisheep

NeoGAF's Chief Barrister
cheezcake said:
Maybe a bit tangential to the point of this thread, but does anyone else here find the concept of a future driven by deep learning quite disappointing?

The technology is incredible, but the fact that when we 'solve' x problem by throwing a paired data set at a big black box and just watch the output til we get what we want and we call it a day.

It's sad right? We dont advance our understanding of the fundamental science or mathematics underlying the problem, it doesn't advance human knowledge in any form really. Maybe it's just an inevitability we've come to as we prod the limitations of the human brain, but that's a depressing realisation in itself.
Click to expand...

I don't find it all that disappointing. It's more like going back to the way things have nearly always been. We live in a privileged time, where we've been brought up to believe that understanding how something works is the key to making use of it - but that has nearly never been the case except in the last few hundred years. Our ancestors sailed ocean-going ships, built great cathedrals, engaged in enormous amounts of trade and fought wars all without understanding elasticity, engineering, ballistics, accountancy, relative density etc etc even to the level that a high-school kid does these days.

You don't have to understand something to be able to use it.
 
cheezcake

cheezcake

Member
phisheep said:
I don't find it all that disappointing. It's more like going back to the way things have nearly always been. We live in a privileged time, where we've been brought up to believe that understanding how something works is the key to making use of it - but that has nearly never been the case except in the last few hundred years. Our ancestors sailed ocean-going ships, built great cathedrals, engaged in enormous amounts of trade and fought wars all without understanding elasticity, engineering, ballistics, accountancy, relative density etc etc even to the level that a high-school kid does these days.

You don't have to understand something to be able to use it.
Click to expand...

Right, but I like understanding things :(
 
S

Somnid

Member
cheezcake said:
I never claimed we don't understand how a neural network fundamentally works, of course we do. The issue is we can't decipher what a trained kernel is actually doing from a conceptual point of view. It's also not really by design, that implies it's intentional we don't want to gather that understanding, it's more of an unintentional consequence.

Your also asserting that the deep learning algorithm in image classification is just using the same classical feature-based algorithms we used to use and the difference is that it just generates the feature classes automatically vs someone manually doing it. That's fundamentally unknown. The point of the deep learning algorithm is it requires absolutely no knowledge of the type of data it's going to be trained with, we don't know what algorithm it's using, whether it's effectively an extension of featured based classification, a significant modification to it, or something different.

I also didn't really say no one was working on it, I mean people are going to, the issue is whether we can decipher the fundamental truths that a trained kernel is operating on and whether we can do it at a pace in which we aren't permanently chasing a target moving faster than us.
Click to expand...

Neuroscience certainly wants this, there's a fair amount of overlap. If we knew how to intuit the neural network then we'll learn more about how our own brains work. On some level though we kinda do. If every perceptron is really just a regressor then we're just building some graph of higher-order features, we just don't know what they actually mean. I think of it as playing a game of Guess Who and trying to figure out the question based on what people were eliminated.

I think in a practical sense it doesn't matter. Let's say we find the one true object detection algorithm. Chances are it's too compute intensive to be useful, we'd have to estimate it, which is what the neural net does and probably why our brains are efficient. So we're probably just skipping a step, but that gets us to the fun part of being able to apply it to problems.
 
P

PantsuJo

Member
Installing cx_Oracle on my Windows laptop was hard as fuck.

First I installed visual studio c++ tools, then Anaconda, then custom python package and finally the updated cx_Oracle whl.

The official methods (pip install or standard whl) were useless for me. Missing DLLs, wrong UTF-8 formatting, nonsensical errors...

Holy shit, it was a nightmare. Dammit Oracle
 
E

Eridani

Member
cheezcake said:
I never claimed we don't understand how a neural network fundamentally works, of course we do. The issue is we can't decipher what a trained kernel is actually doing from a conceptual point of view. It's also not really by design, that implies it's intentional we don't want to gather that understanding, it's more of an unintentional consequence.
Click to expand...

I legitimately don't quite understand what you're trying to say here. If you admit that we know how a neural network works (and not "fundamentally" - we know exactly how it works) then why wouldn't we understand what the trained kernel is doing? If we know how the fitting step works (we do - error optimization just like any other machine learning algorithm) and we know how the prediction step works (we do - just plugging in the fitted kernels back into the equation) then why would we not know what the trained kernel is doing? It's a fundamental part in the whole thing.

Your also asserting that the deep learning algorithm in image classification is just using the same classical feature-based algorithms we used to use and the difference is that it just generates the feature classes automatically vs someone manually doing it. That's fundamentally unknown. The point of the deep learning algorithm is it requires absolutely no knowledge of the type of data it's going to be trained with, we don't know what algorithm it's using, whether it's effectively an extension of featured based classification, a significant modification to it, or something different.
Click to expand...

Why would this be unknown? That's literary what CNNs are doing. That's literary the whole point. Before the softmax layer, CNNs ARE feature extraction. The actual classification is done in the softmax layer, which is very similar to other machine learning approaches (it's basically logistic regression). Or you can just ignore that entirely and replace it with another machine learning algorithm, like SVM and the thing works just fine.

The whole point of CNNs is to train a collection of simple filters that are capable of transforming the image into a simpler representation that will be much easier to classify due to lower dimensionality of the data, and doing this in an ideal way that humans are incapable of.

I found this in 5 minutes of googling, and I think it does a pretty good job of visualizing what CNNs are doing. Relevant quote from the same page:

ConvNets are powerful due to their ability to extract the core features of an image and use these features to identify images that contain features like them. Even with our two layer CNN we can start to see the network is paying a lot of attention to regions like the whiskers, nose, and eyes of the cat. These are the types of features that would allow the CNN to differentiate a cat from a bird for example.
Click to expand...

And then you again say that "we don't know what algorithm it's using", even though we do.

I also didn't really say no one was working on it, I mean people are going to, the issue is whether we can decipher the fundamental truths that a trained kernel is operating on and whether we can do it at a pace in which we aren't permanently chasing a target moving faster than us.
Click to expand...

I mean, you literary said:
The technology is incredible, but the fact that when we 'solve' x problem by throwing a paired data set at a big black box and just watch the output til we get what we want and we call it a day.
Click to expand...
We most definitely do not call it a day. At least, a significant amount of people actually doing research with deep learning do not.
 
AquaticSquirrel

AquaticSquirrel

Member
So I've started learning to use Docker and messing with containers etc... I think I'm getting to grips with the basics but there is something bothering me.

Let's say I create an image for a basic Python web app. Once finished writing the Dockerfile and source code files I build the container and then run it. All working fine.

Let's say I call my container "webapp".

So I realize that I want to add new features to the source code. So I make my changes, save the files and then build the container again with the same name "webapp".

Builds fine and works fine. Great!

But wait... when I run "docker images" I can see my image "webapp" and that's fine, but then underneath it I see an image called <none>

This was the previous build of "webapp". So it looks like by default docker doesn't overwrite the previous image but simply makes a new one if I pass it the -t (tag) flag to tag it as "webapp".

Is there any way that I can force docker to remove old versions/overwrite previous builds automatically?
 
A

Antagon

Member
Wish me good luck guys. Got an interview tomorrow at a small company (30 or so people) that's focussed on logistical software (tracking trucks, optimizing routes, showing upcoming roadwork/expected delays, etc.).

Company is relatively new and works with a nice up to date stack w/ Scala, Akka, Kafka, etc. Coming from my current job at a web development company that does tons of projects with far too less staff, burdened by a ton of tech debt, where I only get the chance to work on maintaining a ton of old stuff in Java it sounds amazing.

The hard part is that I've been at my job for 9 years now and it's been mostly a 9-5 thing. Started out good, I got comfortable, got worse for me the longer I stayed. Moving is overdue, but in the meantime I haven't invested time in building a portfolio or anything. I'm pretty sure I can handle it, now for convincing the people that interview me.
 
K

Kalnos

Banned
Ryujin said:
Is there any way that I can force docker to remove old versions/overwrite previous builds automatically?
Click to expand...

Someone can correct me if I'm wrong but there's no way to not have the <none> images appear. Two commands that get floated around are `docker rmi $(docker images -f dangling=true)` and the newer `docker system prune`. Using those it's easy to remove them if they ever become an issue.
 
T

Two Words

Member
So I understand tail recursion and why if you are doing something with tail recursion, that you should just do it with an iterative loop. That way you don't create new function calls and waste memory. Transitioning from tail recursion to a loop is supposed to be a simple thing, and I often see how it is. But sometimes it seems very difficult to do so. I'll give an example here. How would you change the following recursive function into an iterative function? The function takes an argument that is a string and prints all of the ways to write that word using only periodic table elements.


Code: 
        public static void permutateWord(String targetWord) {
            String elements[] = {"H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar", "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te", "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn", "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm", "Md", "No", "Lr", "Rf", "Db", "Sg", "Bh", "Hs", "Mt", "Ds", "Rg", "Cn", "Uut", "Uuq", "Uup", "Uuh", "Uus", "Uuo"};
            perutateWordHelper(targetWord, "", elements);
        }

        public static void permutateWordHelper(String targetWord, String elemWord, String elements[]) {
            if (targetWord.equalsIgnoreCase(elemWord))
                System.out.println(elemWord);
            else {
	        for (int i = 0; i < elements.length; i++)
	            if (targetWord.toLowerCase().startsWith((elemWord + elements[i]).toLowerCase()))
	                permutateWordHelper(targetWord, elemWord + elements[i], elements);
            }

        }

This seems challenging to do iteratively because it is an arbitrary number of loops and recursion allows you to not worry about that, even if it is tail recursion.
 
M

Makai

Member
Two Words said:
But I want to print all of the ways that you can write a word using periodic element symbols.

Doing a simple while loop also would let me backtrack if one path hits a dead end.
Click to expand...
What's wrong with something like this

Code: 
string targetWord;
string elemWord;

while !targetWord.equalsIgnoreCase(elemWord) {
    // mutate variables
}

print(elemWord);

I haven't really tried to understand the logic but all recursive functions generalize to iterative functions. Just store and mutate variables instead of passing them in as a parameter.
 
T

Two Words

Member
Makai said:
What's wrong with something like this

Code: 
string targetWord;
string elemWord;

while !targetWord.equalsIgnoreCase(elemWord) {
    // mutate variables
}

print(elemWord);

I haven't really tried to understand the logic but all recursive functions generalize to iterative functions. Just store and mutate variables instead of passing them in as a parameter.
Click to expand...


Well it is the // mutate variables part that I can't really figure out. Maybe the problem is that i'm trying to directly translate my tail recursive solution into an iterative one. Usually that is simple to do. But in this case, my recursive solution is basically traversing a tree where each node has elements.length children. It is a depth-first traversal and keeps going deeper as long as it takes it closer to the solution. If it hits a dead end, it just goes back up to the parent node of the node it is at. I don't know if I shouldn't try and carry this tree structure idea with an iterative solution, but It seems like the best way to do it. If I wanted to do an iterative tree traversal, I would need to have a stack, wouldn't I?





The logic of the recursive function is simple. You start with an empty string. Base case. Is that word the word you want? If so, print and end the function. If not, loop through all of the elements. If an the current form of the word + an element is a prefix of the word you want, recursively call the function with that new concatenation.
 
M

Makai

Member
How about this

Code: 
public static void permutateWordHelper(String targetWord, String elemWord, String elements[]) {
    while !targetWord.equalsIgnoreCase(elemWord) {
        bool done;
        
        for (int i = 0; i < elements.length && !done; i++) {
            if (targetWord.toLowerCase().startsWith((elemWord + elements[i]).toLowerCase())) {
                elemWord += elements[i];
                done = true;
            }
        }
    }

    print(elemWord);
}

You can replace the done boolean with a continue or break but I knew I'd probably get it wrong.
 
T

Two Words

Member
Makai said:
How about this

Code: 
public static void permutateWordHelper(String targetWord, String elemWord, String elements[]) {
    while !targetWord.equalsIgnoreCase(elemWord) {
        bool done;
        
        for (int i = 0; i < elements.length && !done; i++) {
            if (targetWord.toLowerCase().startsWith((elemWord + elements[i]).toLowerCase())) {
                elemWord += elements[i];
                done = true;
            }
        }
    }

    print(elemWord);
}

You can replace the done boolean with a continue or break but I knew I'd probably get it wrong.
Click to expand...

There are a couple of problems. This will only find one way to spell a word with periodic element symbols. My recursive function is designed to find all ways. And even if a word had an arbitrary number of ways to be spelled with the symbols greater than 0, this function may not find it. I see no ability for this iterative solution to backtrack if it hits a dead end and continue again from a previous state.

Let's use "ber" as an example.

It would say that Be works
But then it would find no way to concatenate Be and anything else to prefix "ber". I guess the would actually cause an infinite loop.


But if it could back track and eventually start with just B
It could then eventually reach BEr
 
C

cpp_is_king

Member
keep a set of unused symbols and the current word, and Just make a while loop over all unused symbols. Append the current symbol to the current word, remove it from the set of available symbols, and recurse. When you hit a dead end, check if it's a valid word and add it to the set of valid words.

Iterative algorithm is exactly the same except instead of "recurse" it's "push the set of unused symbols onto a stack"
 
T

Two Words

Member
cpp_is_king said:
keep a set of unused symbols and the current word, and Just make a while loop over all unused symbols. Append the current symbol to the current word, remove it from the set of available symbols, and recurse. When you hit a dead end, check if it's a valid word and add it to the set of valid words.

Iterative algorithm is exactly the same except instead of "recurse" it's "push the set of unused symbols onto a stack"
Click to expand...
By unused do you mean as if to spell the word without using the same element twice? Because I am not trying to do that. I am allowing the same element to be used multiple times.


If it is not what you mean, wouldn't using a stack structure essentially have the same memory effects of a recursive solution? I'm sure a stack would be a more memory efficient solution, but it would still use an increasing amount of memory for larger strings.
 
K

Koren

Member
Two Words said:
So I understand tail recursion and why if you are doing something with tail recursion, that you should just do it with an iterative loop. That way you don't create new function calls and waste memory. Transitioning from tail recursion to a loop is supposed to be a simple thing, and I often see how it is. But sometimes it seems very difficult to do so. I'll give an example here. How would you change the following recursive function into an iterative function? The function takes an argument that is a string and prints all of the ways to write that word using only periodic table elements.
Click to expand...
I'll admit I don't understand:
- your recursive function isn't tail recursive (in fact, it's hard to do tail-recursive functions when a call can do more than one recursive call, which is the case here)
- if a function is tail-recursive (and assuming the language support it), there's very little advantage to turn it into a loop (and you can indeed swap the calls for a stack)
 
T

Two Words

Member
Koren said:
I'll admit I don't understand:
- your recursive function isn't tail recursive (in fact, it's hard to do tail-recursive functions when a call can do more than one recursive call, which is the case here)
- if a function is tail-recursive (and assuming the language support it), there's very little advantage to turn it into a loop (and you can indeed swap the calls for a stack)
Click to expand...
I thought my function is tail recursion because the recursion is done last and the desired result is achieved at the base case, not after building back up from the base case. Are you saying that it isn't tail recursion by definition because it is in a for loop?
 
K

Koren

Member
Two Words said:
If it is not what you mean, wouldn't using a stack structure essentially have the same memory effects of a recursive solution?
Click to expand...
Comparable effects, yes.

Two Words said:
I'm sure a stack would be a more memory efficient solution
Click to expand...
Not that much...

Two Words said:
but it would still use an increasing amount of memory for larger strings.
Click to expand...
That's assuming there's another solution...

Would you mind giving an example of the input (a sring, I get) and the output you want? You want all solutions printed, like
C O Ca
Co Ca

?
 
K

Koren

Member
Two Words said:
I thought my function is tail recursion because the recursion is done last
Click to expand...
Well, it's the last line, but it's not the last computation done...

It's inside a loop, so you have code after the call. Even more so if the call isn't the last iteration of the loop (but even if it is the case, the check to see whether the loop it finished is done after the call, so no tail-elimination possible)

Two Words said:
Are you saying that it isn't tail recursion by definition because it is in a for loop?
Click to expand...
Yes.

Edit: a quick rule of thumb: as long as a function can call itself more than once, it can't be tail recursive (or at the very least, it won't be except MAYBE for the last call, but that depends on the code). And if it's not fully tail-recursive, it's probably useless to have it partly tail-recursive.
 
T

Two Words

Member
Koren said:
Comparable effects, yes.


Not that much...


That's assuming there's another solution...

Would you mind giving an example of the input (a sring, I get) and the output you want? You want all solutions printed, like
C O Ca
Co Ca

?
Click to expand...

Let's say you input "nono"

You would expect the following to print on the screen

NONO
NONo
NoNO
NoNo

Koren said:
Well, it's the last line, but it's not the last computation done...

It's inside a loop, so you have code after the call. Even more so if the call isn't the last iteration of the loop (but even if it is the case, the check to see whether the loop it finished is done after the call, so no tail-elimination possible)


Yes.

Edit: a quick rule of thumb: as long as a function can call itself more than once, it can't be tail recursive (or at the very least, it won't be except MAYBE for the last call, but that depends on the code). And if it's not fully tail-recursive, it's probably useless to have it partly tail-recursive.
Click to expand...

That makes sense. Well that would explain why it was so difficult to convert it into an iterative solution.
 
S

Spoiled Milk

Banned
Two Words said:
So I understand tail recursion and why if you are doing something with tail recursion, that you should just do it with an iterative loop. That way you don't create new function calls and waste memory. Transitioning from tail recursion to a loop is supposed to be a simple thing, and I often see how it is. But sometimes it seems very difficult to do so. I'll give an example here. How would you change the following recursive function into an iterative function? The function takes an argument that is a string and prints all of the ways to write that word using only periodic table elements.


Code: 
        public static void permutateWord(String targetWord) {
            String elements[] = {"H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar", "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te", "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn", "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm", "Md", "No", "Lr", "Rf", "Db", "Sg", "Bh", "Hs", "Mt", "Ds", "Rg", "Cn", "Uut", "Uuq", "Uup", "Uuh", "Uus", "Uuo"};
            perutateWordHelper(targetWord, "", elements);
        }

        public static void permutateWordHelper(String targetWord, String elemWord, String elements[]) {
            if (targetWord.equalsIgnoreCase(elemWord))
                System.out.println(elemWord);
            else {
	        for (int i = 0; i < elements.length; i++)
	            if (targetWord.toLowerCase().startsWith((elemWord + elements[i]).toLowerCase()))
	                permutateWordHelper(targetWord, elemWord + elements[i], elements);
            }

        }

This seems challenging to do iteratively because it is an arbitrary number of loops and recursion allows you to not worry about that, even if it is tail recursion.
Click to expand...

You've got it slightly wrong here. Any tail recursive function can be turned into an iterative one and vice versa. But your function is not tail recursive. Remember that tail recursion means returning from a tail call, i.e. the very last function call in your function. Maybe it's harder to see this because you're not returning anything at all (I suspect this is because you wanted to get the algorithm right first). Your function still has "work to do" after every recursive call.

Putting things in terms of work is maybe the easiest way to understand when and why recursive functions can be made into iterative ones. Iteration takes up a fixed amount of work space / stack space - the loop body or function body. But your function has a variable amount of work to do, dynamically, depending on what element names are valid. Recursion is the proper technique here for the method you're using; that is, constructing strings combinatorically from the element names.

Tail recursion is a funny story. Once upon a time, function calls were deemed expensive, and so inlining the body of the function instead of calling it was deemed preferable. This was not about recursion, but about how wasteful function calls were. Guy Steele and Gerald Sussman were designing a language called Scheme at the time and showed in a famous paper that if you were returning the result of a function call, because there were no operations left to be performed on it, you could simply just reuse the entire stack frame - no expensive function call, stack frame allocation, and copying needed. That's any function call, mind you, not just recursive ones. Thus tail call elimination was born. And concurrently of course it was known that you could write iterative functions as recursive ones by passing the state along. So the addition of tail call elimination meant that tail call recursive functions were as good as loops. Neat, said the authors of Scheme.
 
T

Two Words

Member
Spoiled Milk said:
You've got it slightly wrong here. Any tail recursive function can be turned into an iterative one and vice versa. But your function is not tail recursive. Remember that tail recursion means returning from a tail call, i.e. the very last function call in your function. Maybe it's harder to see this because you're not returning anything at all (I suspect this is because you wanted to get the algorithm right first). Your function still has "work to do" after every recursive call.

Putting things in terms of work is maybe the easiest way to understand when and why recursive functions can be made into iterative ones. Iteration takes up a fixed amount of work space / stack space - the loop body or function body. But your function has a variable amount of work to do, dynamically, depending on what element names are valid. Recursion is the proper technique here for the method you're using; that is, constructing strings combinatorically from the element names.

Tail recursion is a funny story. Once upon a time, function calls were deemed expensive, and so inlining the body of the function instead of calling it was deemed preferable. This was not about recursion, but about how wasteful function calls were. Guy Steele and Gerald Sussman were designing a language called Scheme at the time and showed in a famous paper that if you were returning the result of a function call, because there were no operations left to be performed on it, you could simply just reuse the entire stack frame - no expensive function call, stack frame allocation, and copying needed. That's any function call, mind you, not just recursive ones. Thus tail call elimination was born. And concurrently of course it was known that you could write iterative functions as recursive ones by passing the state along. So the addition of tail call elimination meant that tail call recursive functions were as good as loops. Neat, said the authors of Scheme.
Click to expand...
The fact that it isn't really tail recursionakes sense now. Plus, I guess the base case doesn't really find me the answer, but only one part of the answer. In this case the answer I am trying to get is all of the ways that it can be spelled with elements. I've read that some compilers will take the recursion out of tail recursion for you, but I'm not sure how standard that is.
 
K

Koren

Member
Two Words said:
Let's say you input "nono"

You would expect the following to print on the screen

NONO
NONo
NoNO
NoNo
Click to expand...
You won't find a solution that is more efficient memory-wise than the stack one...

And honestly, the stack one IS memory-efficient. It's basically O(n), and you won't find a better solution than O(n), you can't get this result without storing the chain.

Of course, you need more than the chain... But the stack can be a stack of bits (0 = single character, 1=double caracter, so NONO is 1111, NONo is 110, NoNO is 011, NoNo is 11). Add in the size of the stack, and you basically need only 15% more memory than the memory needed to store the string (well, 25% if you encode the string into something more efficient than ASCII, but...)

Reducing the memory footprint has a cost computation-wise. But with just twice the memory used to store the string, you have an efficient solution (just use a stack of int8, since all elements can be stored as int8)

Two Words said:
That makes sense. Well that would explain why it was so difficult to convert it into an iterative solution.
Click to expand...
Indeed...

Though it's not difficult, it's always the same:
- put the function into a while loop, whose condition is "while not stack_empty"
- retrieve arguments using pop
- do the computation, and for each call, push arguments on the stack
- ...
- profit*

(*or no profit, in fact, in most cases)

But if you mean a stack-less solution, yes, it should be hard.
 
C

cpp_is_king

Member
Two Words said:
By unused do you mean as if to spell the word without using the same element twice? Because I am not trying to do that. I am allowing the same element to be used multiple times.


If it is not what you mean, wouldn't using a stack structure essentially have the same memory effects of a recursive solution? I'm sure a stack would be a more memory efficient solution, but it would still use an increasing amount of memory for larger strings.
Click to expand...

If your'e allowing the same element twice how do you decide when to terminate? Is there a maximum word length?
 
T

Two Words

Member
cpp_is_king said:
If your'e allowing the same element twice how do you decide when to terminate? Is there a maximum word length?
Click to expand...

Well my recursive solution does end. Let's just assume that there are 120 elements. Imagine a complete 120-ary tree that goes on infinitely. Every node represents some permutation of periodic elements, with replacement. Think of the root as the empty string. Every child of every node is one of the periodic elements. My recursive algorithm does a depth-first search. If concatenating the parent node string with the child node string is a prefix of the desired word, we go down the tree recursively. Whenever we eventually come back, we try the next child. When all children are checked, we go back up. The base case is when the desired word has been reached. If a parent has no child which fits these parameters, no recursive call is made at this parent.

If you tried "AAAAAA", no recursive call would ever be made because there is no periodic element that is the prefix of "AAAAAA". The tree traversal only goes as long as is needed to spell the word. So if N is the length of the string, then there will never be more than N recursive calls in memory at any given time.
 
K

Koren

Member
cpp_is_king said:
If your'e allowing the same element twice how do you decide when to terminate? Is there a maximum word length?
Click to expand...
The word is predefined, it's just a matter of finding all the way to cut it...

There's fibo(n) possible divisions of the word into 1-letter and 2-letters parts, you just have to find all divisions whose all parts are in a set (duplicates allowed).

The recursion ends because arguments of all recursive calls are strictly shorter than the original one, (and empty string don't make recursive calls, although you don't need this detail to prove the termination)
 
AquaticSquirrel

AquaticSquirrel

Member
Kalnos said:
Someone can correct me if I'm wrong but there's no way to not have the <none> images appear. Two commands that get floated around are `docker rmi $(docker images -f dangling=true)` and the newer `docker system prune`. Using those it's easy to remove them if they ever become an issue.
Click to expand...

Ah right, so I need to manually clean up the old images and containers using one of those commands.

Kind of annoying, you'd imagine that for code that is in development and will need many iterations that the docker developers would have come up with a better solution.

Not the end of the world really but just means I have more things to think about cleaning up after I'm done.
 
C

cpp_is_king

Member
Koren said:
The word is predefined, it's just a matter of finding all the way to cut it...

There's fibo(n) possible divisions of the word into 1-letter and 2-letters parts, you just have to find all divisions whose all parts are in a set (duplicates allowed).

The recursion ends because arguments of all recursive calls are strictly shorter than the original one, (and empty string don't make recursive calls, although you don't need this detail to prove the termination)
Click to expand...

Ahh I missed that. So in that case do something like this, it only keeps a single stack which is the current spelling, but which never uses more space than the input string. Normally you need an additional stack to mimic the fact that each level of a recursion has a loop, and you need to remember where you are in that loop. So you have N levels of "how many elements have I processed so far?" But in this case we can use the fact that items in a periodic table are numbered to eliminate this requirement, and have our loop state be entirely determined just by knowing which periodic table element we just looked at.

Code: 
struct Element {};  // one periodic table element
struct Spelling {};  // sequence of Elements

vector<Spelling> findSpellings(string Input) {

  stack<Element> CurrentSpelling;
  StringView Suffix = Input;
  while (true) {

    if (spellingMatchesInput(CurrentSpelling, Input)) {
      // Found a valid spelling.  Print it, remove the last item,
      // and keep trying.
      printSpelling(CurrentSpelling);
      Suffix.unskip(CurrentSpelling.top().Symbol.size());
      CurrentSpelling.pop();
      continue;
    }

    Element Next;

    if (CurrentSpelling.empty())
      Next = PeriodicTable[0];
    else {
      Element Top = CurrentSpelling.top();
      if (Top.PeriodicNumber >= PeriodicTable.size()) {
        // We've tried every possible element at this level, and
        // cannot find a spelling.  Go back one.
        Suffix.unskip(CurrentSpelling.top().Symbol.size());
        CurrentSpelling.pop();
        continue;
      }
      Next = PeriodicTable[Top.PeriodicNumber + 1];
    }

    // The current symbol does not lead to a valid spelling.  Ignore it
    // but keep trying at the current level.
    if (!Suffix.starts_with(Next.Symbol))
      continue;
    
    // We found a longer prefix!
    Suffix.skip(Next.Symbol.size());
    CurrentSpelling.push(Next);
  }
}


You can improve upon this further by instead by pre-computing the list of all possible valid prefixes. Before the loop, iterate the periodic table [which is O(1)] and remove those items which are not a substring of the input string. Then instead of saying

Next = PeriodicTable[Top.PeriodicNumber + 1];

you would say something like

Next = ValidElements.find(Top) + 1;

with various other micro-optimizations possible (like making Element a linked list or something)
 
K

Koren

Member
I had some free time this morning, so...


Just as an exercise, it IS possible to make a tail-recursive function that display all possibilities AND to use only an integer and a bool in addition of the string.

For example, in Caml (I don't have a java compiler handy, and I definitively don't like Java ;) ), for 1 and 2 letters elements (I'm sure it can be done for 3-letters element, but it would really become awful):
Code: 
let elems = [ "H"; "HE"; "LI"; "BE"; "B"; "C"; "N"; "O"; 
              "F"; "NE"; "NA"; "MG"; "AL"; "SI"; "P"; "S"; 
              "CL"; "AR"; "K"; "CA"; "SC"; "TI"; "V"; "CR"; 
              "MN"; "FE"; "CO"; "NI"; "CU"; "ZN"; "GA"; 
              "GE"; "AS"; "SE"; "BR"; "KR"; "RB"; "SR"; 
              "Y"; "ZR"; "NB"; "MO"; "TC"; "RU"; "RH"; 
              "PD"; "AG"; "CD"; "IN"; "SN"; "SB"; "TE"; 
              "I"; "XE"; "CS"; "BA"; "LA"; "CE"; "PR"; 
              "ND"; "PM"; "SM"; "EU"; "GD"; "TB"; "DY"; 
              "HO"; "ER"; "TM"; "YB"; "LU"; "HF"; "TA"; 
              "W"; "RE"; "OS"; "IR"; "PT"; "AU"; "HG"; 
              "TL"; "PB"; "BI"; "PO"; "AT"; "RN"; "FR"; 
              "RA"; "AC"; "TH"; "PA"; "U"; "NP"; "PU"; 
              "AM"; "CM"; "BK"; "CF"; "ES"; "FM"; "MD"; 
              "NO"; "LR"; "RF"; "DB"; "SG"; "BH"; "HS"; 
              "MT"; "DS"; "RG"; "CN" ];;

let Disp ch =
  let n = string_length ch in
  let rec Foo = fun
    | p _ when p<0 -> ()
    
    | p _ when p=n -> print_string ch;
                      print_newline ();
                      Foo (p-1) false
    
    | p true -> if mem (sub_string ch p 1) elems
                  then Foo (p+1) true else Foo p false
    
    | p false when ch.[p] >= `a`
      -> ch.[p] <- char_of_int (int_of_char ch.[p] - 32);
         Foo (p-2) false
    
    | p false when p < n-1 && ch.[p+1] <= `Z` 
      && mem (sub_string ch p 2) elems
      -> ch.[p+1] <- char_of_int (int_of_char ch.[p+1] + 32);
         Foo (p+2) true
    
    | p false -> Foo (p-1) false

  in Foo 0 true;;

For example,
Code: 
Disp "COCACOLA";;
produces
Code: 
COCAcOLa
COCaCOLa
COCaCoLa
CoCAcOLa
CoCaCOLa
CoCaCoLa
- : unit = ()

Since it's tail-recursive, it's dead-easy to convert it into a loop, with no required storage beside the integer and the boolean...

Code: 
let Disp ch =
  let n = string_length ch 
  and pos = ref 0 and fwd = ref true in
    while !pos >= 0 do
      if !pos=n
        then begin
               print_string ch; print_newline (); 
               pos := !pos - 1
             end
      else if !fwd && mem (sub_string ch !pos 1) elems
        then pos := !pos + 1
      else if !fwd
        then fwd := false
      else if ch.[!pos] >= `a` 
        then begin
               ch.[!pos] <- char_of_int (int_of_char ch.[!pos] - 32);
               pos := !pos-2
             end
      else if !pos < n-1 && ch.[!pos+1] <= `Z` && mem (sub_string ch !pos 2) elems
        then begin
               ch.[!pos+1] <- char_of_int (int_of_char ch.[!pos+1] + 32);
               pos := !pos + 2;
               fwd := true
             end
      else pos := !pos-1
    done;;


Edit: I'm thinking that people haven't probably played much with ML languages, so just a warning: !fwd is not the negation of the boolean forward, !x is just the way you get the content of the variable x...

I'm willing to rewrite it in C if someone is interested (even if Java is you REALLY want it)
 
W

wwm0nkey

Member
It's not too expensive so I'm probably going to do it, but anyone know if it's worth it getting the .Net certification from Microsoft? I mean I know certs are sometimes and will probably look really nice with my past job and associate's degree in IT. I mostly want to do it to give me a reason to read a book and learn more about C# and the .Net Framework though
 
C

cpp_is_king

Member
Clever, from a high level it looks more or less the same as what I described by using the periodic number as an ordering, but you're mutating the input string to avoid keeping an extra stack
 
P

PantsuJo

Member
Guys, I need you help. Thanks in advance for your assistance.

I'm developing with Python 3.6 and cx_Oracle (for Oracle DB).

My script works well so I wanted to create a standalone exe using cx_freeze, capable of running on any Windows machine.

I don't know why but everytime I launch the exe the program cannot import the cx_Oracle module, despite the ".py", ".pyc" and ".pyd" files being placed in the executable dir.

I already compiled few applications using cx_freeze and everytime they launched flawlessly on every system but here, damn, it seems impossible to include ALL the necessary files for cx_Oracle.

How can I solve? Have you past experiences with Python and this Oracle module?
 
K

Koren

Member
cpp_is_king said:
Clever, from a high level it looks more or less the same as what I described by using the periodic number as an ordering, but you're mutating the input string to avoid keeping an extra stack
Click to expand...
That's exactly it... And since I'll have to change the input (or a copy of the input) for printing purpose (or keep a copy of all elements since the beginning), using it to keep track of the "calls" by using lowercase/uppercase was a possibility.

Though:
- it's probably hard to maintain and extend
- there's no big gain in terms of memory (unless a factor 2x is important*)
- it can be a bit slower (instead of doing large jumps back when a call returns, I have to do it 2 chars by 2 chars), though that doesn't change the complexity

It's basically to check that it could be done...

(*) and I doubt the 2x in space can be important when space complexity is O(n) and time complexity is O(a^n)



There's some interesting parts in there, though. It's basically the same thing as creating a Turing automaton that increment an integer, except that you "jump" whole ranges of numbers in some cases.

In fact, the result is almost a Turing automaton (though you access the character at pos+1 and pos+2, and that would require some adjustments)


There's actually more to do with this than what I expected when I saw this as a coding exercise... A lot of theorical stuff.


And also, since it's basically a fibonacci tree that we're exploring, I came to wonder: is there an easy/eficient way to convert an integer k between 0 and fibo(n)-1 into a binary value that corresponds to the path (0 = left child, 1 = right child) to reach the node k in a fibonacci tree, the nodes being numbered using DFS exploration?
 
K

Koren

Member
PantsuJo said:
How can I solve? Have you past experiences with Python and this Oracle module?
Click to expand...
Not trying to include it in a cx_Freeze executable...

Would you mind posting the setup.py file you use for the freeze? Not sure I'll be able to help, but one can try...

You can get the executable, then get an import error at runtime?
 
P

PantsuJo

Member
Koren said:
Not trying to include it in a cx_Freeze executable...

Would you mind posting the setup.py file you use for the freeze? Not sure I'll be able to help, but one can try...

You can get the executable, then get an import error at runtime?
Click to expand...
Oh, yes, of course I didn't include cx_freeze in the setup script, don't worry, it's a typo error lol

I'll post it later, thanks in advance for your help!
 
D

dawgparty

Member
This is an annoying post so sorry, but any recs for fun projects/websites/etc. to use for learning Java the first time? I took a few classes on it in college and was not feeling it but I'd like to give it another chance.
 
K

Koren

Member
PantsuJo said:
Oh, yes, of course I didn't include cx_freeze in the setup script, don't worry, it's a typo error lol
Click to expand...
No, I meant I've used a bit cx_Oracle some time ago, cx_Freeze recently, but I never tried to freeze a python program that include cx_Oracle. I still don't understand fully how cx_Freeze works, and I fully expect those modules that depends on binaries to be tricky to package...
 
You must log in or register to reply here.

Similar threads

Nvidia reports record earnings, profits on growth in AI and gaming
Business Analysis Hardware 2
68
4K
FStubbs replied
Dave the Diver |OT| Life is better, down where's it wetter
|OT| Indie 2 3
125
8K
Maiden Voyage replied
WWE and Endeavor (UFC) announce 21 billion dollar deal.
40
2K
thefool replied
A Windows user's experiences with Linux (should you switch?)
Opinion Analysis 2 3 4
190
13K
twilo99 replied
The State of Xbox Game Studios and Bethesda Softworks: A breakdown of all the Confirmed Projects, Leaks, and Rumors
Opinion News Rumor 2
84
9K
Ozriel replied
Top Bottom