PetriP-TNT
Member
But javadocs say in Deque.element():
??
Doesn't that make peek, getfirst and element the same (minus element/getFirst throwning exception and peek returning null?)
-
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
- Thread starter Kikarian
- Start date
But javadocs say in Deque.element():
??
Doesn't that make peek, getfirst and element the same (minus element/getFirst throwning exception and peek returning null?)
ChocolateCupcakes
Member
Well yeah it will return a different exception. getFirst is only for the head of the queue while peek is more universal in that you can traverse the list and get an element without messing up your queue/linked list. I wouldn't think of them as the same at all.
hawkshockey11
Banned
hackathon went okay. We used openCV to make a bus stop detector to count how many people are waiting for the bus at each stop and putting that information into a formula for a priority route if the bus is empty. 1st place winner was not that good honestly. They took an open source game and edited it a little to simulate an app using some of the phones processing power as a hive for a research computer. Similar to folding @ home and others. They just didn't do much besides talk about the idea while playing the game.
I got it so its working for words with no duplicate letters, but for some reason my program is still off when their is duplicate letters. Here's my code:I can see how to do it relatively efficiently. starting at the end of the string with only one character to 'choose' you so far have a rank of 0 (number 1, top rank) and have only 1 permutation. furthermore you have a total of 1 character to choose from and it's weight is 1, store this information somewhere
working backward through the string for each character, add this character to the list, if we let n be the number of permutations of our previous substring then
this substring will have n * (n+1) / k substrings where k is the count for the character we added at this point.
If you look at the alphabetical ordering of this character compared to the list of available characters then you take the sum of the counts of all of the characters that precede the current character alphabetically, multiply them by n. add this value to your current rank.
repeat this process and you should have a rank that is off by 1. add 1.
Example:
Let our string be apple
starting at e we have 1 permutation and 1 instance of e. we have rank 0
looking at l, we add p to the list of characters, giving it a count of 1
this means at this point there are 2 permutations
also, l is after e so we take 2 / 2 * 1 = 1
our rank is 1
next up is p, p is new too so it gets a count of 1
2 * 3 / 1 = 6 permutations for 'ple'
p is worse than both l and e so 6 / 3 * 2 = 4
our rank is now 5
a second p, p's count goes up to 2
6 * 4 / 2 = 12 permutations for 'pple'
again, p is worse than both l and e
12 / 4 * 2 = 6
our rank is now 11
finally the a, a is better than everybody
12 * 5 / 1 = 60
a is better than everyone, we add nothing to our rank
our final rank is 11
lets check the 'pple' substring because checking all 60 permutations for apple will be tiresome
elpp, eplp, eppl, lepp,
lpep, lppe, pelp, pepl,
plep, plpe, ppel, pple
that looks like a complete list of 12 to me, and with pple as the final element in that list, number 12, 11+1. Also, since apple starts with a, it can't lose rank so
apple must have the same rank, and it does.
since it works this time it must work every time
You can save a division by multiplying the new permutation by (n+1) after the rank at this point has been calculated. which is also preferrable because it means for the last (and thus largest) number of permutations you can avoid calculating that whole number, which could, in all probability wind up breaking your 64 bit barrier even if you're given a string with a rank that's under the limit.
Code:
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class WordRanking {
static int getRank(String input, int count) {
if (input.length() == 1) return 1;
else {
int n = input.length();
String remainder = input.substring(1);
if (n > 2) {
return count * factorial(n-1)/factorial(getDuplicateCount(input)) + getRank(remainder, getCount(remainder));
}
else {
return count * (n-1) + getRank(remainder, getCount(remainder));
}
}
}
static int getCount(String input) {
int count = 0;
char c = input.charAt(0);
char[] charArray = input.toCharArray();
for (int i = 1; i < charArray.length; i++) {
if(charArray[i] < c) {
count++;
}
}
return count;
}
static int getDuplicateCount(String input) {
int totalCount = 0;
char inputArray[]=input.toCharArray();
HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
for(int i = 0; i < inputArray.length; i++) {
char inputChar = inputArray[i];
hm.put(inputChar, (hm.get(inputChar)==null?0:hm.get(inputChar)+1));
}
Set<?> set = hm.entrySet();
Iterator<?> i = set.iterator();
while(i.hasNext()) {
Map.Entry<Character, Integer> me = (Map.Entry<Character, Integer>)i.next();
totalCount = totalCount + me.getValue();
}
//System.out.println(totalCount);
return totalCount;
}
static int factorial(int f) {
return ((f == 0) ? 1 : f * factorial(f - 1));
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
String word = "";
do {
System.out.println("Enter any word. Word must be no more than 25 letters:");
word = scanner.nextLine();
word.toUpperCase();
if (word.equals(""))
System.out.println("You haven't entered a word yet.");
} while (word.equals("") || word.length() >= 25);
System.out.println(getRank(word, getCount(word)));
scanner.close();
}
}I'm not sure why it's not working with repeating letters. Is the way I'm calculating the duplicate count wrong in the getDupCount method?
I have a class that writes to a file but needs to access members from another class:
How would I exactly access the data members from the Other & r class so I can use those to print on to the file? If I make it a friend, it doesnt even know the Other class and if I dont make it a friend, it says the data members are private
Code:
long write(const Other &r, bool flag, int type);How would I exactly access the data members from the Other & r class so I can use those to print on to the file? If I make it a friend, it doesnt even know the Other class and if I dont make it a friend, it says the data members are private
Make them public.
It seems like you're summing your character counts? like if you had aapple your getduplicatecount would give you 2 (1 for a, 1 for p, 0 for l, and 0 for e) and you would calculate 2! when what you want is 2! * 2! * 1! * 1!. if you set your hashmap 0 to 1 and turned your addition to a *= factorial(thehashedintishere) you should see the right result.
also I would make sure to test large strings because I think that generating that big n-1 factorial is going to get you in trouble.
Edit: also also, I would turn the ints that have anything to do with the factorial values and final rank into longs. eg, your factorial method should take and return a long.
Dunno... this just seemed like a nicer and faster way for it to be done...
Alright, Programming-GAF. I've got a question for you regarding collision with rectangles for the game I'm making (it's a Achtung die kurve-clone, or http://curvefever.com/ if you know that). Our player bodies are represented by tiny rectangles and I want to check for collision between these (if a player runs into another player's body).
As you can see in this picture, I have the coordinates of the four corners of each rectangle. They're numbered as you can see. Now, how do I go about checking for collision? For my first attempt I tried something like this:
but it's all just a mess and works like 10% of the time.
Anyone got any idea how to implement this well?
As you can see in this picture, I have the coordinates of the four corners of each rectangle. They're numbered as you can see. Now, how do I go about checking for collision? For my first attempt I tried something like this:
Code:
((thisx1 >= otherx1 && thisx1 >= otherx2
&& thisx1 <= otherx3 && thisx1 <= otherx4) && (thisy1 >= othery1
&& thisy1 <= othery2 && thisy1 <= othery3 && thisy1 >= othery4))
|| ((thisx2 >= otherx1 && thisx2 >= otherx2
&& thisx2 <= otherx3 && thisx2 <= otherx4) && (thisy2 >= othery1
&& thisy2 <= othery2 && thisy2 <= othery3 && thisy2 >= othery4))
|| ((thisx3 >= otherx1 && thisx3 >= otherx2
&& thisx3 <= otherx3 && thisx3 <= otherx4) && (thisy3 >= othery1
&& thisy3 <= othery2 && thisy3 <= othery3 && thisy3 >= othery4))
|| ((thisx4 >= otherx1 && thisx4 >= otherx2
&& thisx4 <= otherx3 && thisx4 <= otherx4) && (thisy4 >= othery1
&& thisy4 <= othery2 && thisy4 <= othery3 && thisy4 >= othery4)))but it's all just a mess and works like 10% of the time.
Anyone got any idea how to implement this well?
PetriP-TNT
Member
edit: nevermind again, too tired to think
Out of curiosity - the game you mention as reference is obviously not using box-collision, are you sure you actually need to do it this way?Jokab said:
Anyway, what you're looking for is OBB(Oriented Bounding Box) collision/overlap check - your code is roughly what you'd do to test Axis Aligned boxes (which is why it works "sometimes").
For OBB, there should be plenty of google resources on the topic - I recommend you read up on it first (the code for optimized solution is some vector math and 10 conditional-statements or so in 2d - but I don't think it's a good learning resource if you've never done this before).
You don't have to redirect them, you can just store the session variable and wait for them to refresh the page. Unless it's required for something.
When you say the player body, you don't mean the lines they leave behind do you?
what's been said above is correct. I'll add that if you're going to do vector shapes you might want to use a circle instead. the logic would be that if the distance between two circle origins are less than 2r (or if you're allowing them to have different radii r_1 + r_2). or actually if
if
(o1x - o2x) ^ 2 + (o1y - o2y) ^ 2 < (r1 + r2) ^2
then intersection. regardless of rotation
3 mults. 2 adds, 2 subs (well, implied subtraction in the comparison too but hey), every time.
but I wouldn't even use a vector for something like that, especially with those tails. something more like blitting, or literally trying to draw your character against a hidden surface (or potentially even the displayed surface) that records these things.
I got it working, thanks for the help.
Randolph Freelander
Member
As part of my foray into getting up to speed on Comp Sci topics that I haven't been exposed to in my academic background or programming career, I'm following an MIT course that uses Python as its language.
I don't think I like Python, despite how easy it is. The design decisions here might sit well with certain crowds, because, hey, we're all different, but I can't believe there's apparently no real concept of private members, nor is there any real type safety. And I recently learned that apparently the creator of Python has no real issue introducing crazy breaking changes between versions. That part is upsetting, the previous items are simply points of disagreement, I suppose.
I could see its usefulness for some quick scripting type activities, a playground or prototyping tool, things like that. And then take that prototype and implement it using a different language altogether.
I don't think I like Python, despite how easy it is. The design decisions here might sit well with certain crowds, because, hey, we're all different, but I can't believe there's apparently no real concept of private members, nor is there any real type safety. And I recently learned that apparently the creator of Python has no real issue introducing crazy breaking changes between versions. That part is upsetting, the previous items are simply points of disagreement, I suppose.
I could see its usefulness for some quick scripting type activities, a playground or prototyping tool, things like that. And then take that prototype and implement it using a different language altogether.
Yep, all true. As for typing, if you're referring to dynamic typing then yeah you'll find a lot of popular languages that way, like Ruby and Javascript (Dynamic Typing). As in, nothing stops you from calling a method with an incompatible object; you just get a runtime error.
Dynamic typing is really, really tough to use in a large project coming from a statically typed language. And it can make tooling a lot more difficult (intellisense, etc).
I'm not totally against the breaking changes thing, especially if the alternative is being stuck with some terrible aspects forever (Java). But it has definitely caused a rift for several years while libraries are rewritten, etc. I think a lot of modern languages have that approach, introducing breaking changes in major versions. They just try to keep it to an absolute minimum. Also, if a language is compiled then usually you can retain binary compatibility (or version the runtime). With interpreted languages with one monolithic interpreter like python, breaking changes are a lot worse.
Randolph Freelander
Member
I, too, can deal with breaking changes, as long as they make sense.
Case in point, and I used this example earlier today when I was talking with a colleague: C# 4 to C# 5 foreach loops.
It's not precisely this, but in C# 4 and previous, the loop variable was considered as declared outside the loop. So something like
Was functionally like
Again, it's not precisely that, it's obviously not in scope outside of the loop in reality, but you get the point.
In C# 5, that has changed. The loop variable is considered new with each iteration, declared inside each iteration. Now it's more like
And the reason this was changed between C# 4 and 5 was because of closures. People, and apparently a lot of them, were closing over the loop variable inside the loop and then doing evaluations of those closures outside the loop and were getting unexpected results. Closures close over the variables, not values, so what they were finding was at the end of it all, they had basically a bunch of closures that produced the same output because they were all referencing the same variable that would obviously hold the same value.
So for C# 5, they changed it so that people would see their programs work as they expected. The caveat, of course, is that if anyone was actually relying upon the previous behavior, it just broke. But at least it's a breaking change that makes sense.
In Python, apparently between 2 and 3 they decided to change division semantics between integers. In Python 2.x, it uses the same integer math you are accustomed to if you use languages like C#, Java, etc.
It prints 0.
In Python 3.x, they decided to have it perform floating point math, which changes the output.
And you get 0.66666...
Frustrating. Now people that were actually relying upon integer division (think midpoint finding, just for one use case) have to go and fix who knows how many places inside their code.
Case in point, and I used this example earlier today when I was talking with a colleague: C# 4 to C# 5 foreach loops.
It's not precisely this, but in C# 4 and previous, the loop variable was considered as declared outside the loop. So something like
Code:
foreach(string item in list)
{Was functionally like
Code:
string item;
foreach (item in list)
{Again, it's not precisely that, it's obviously not in scope outside of the loop in reality, but you get the point.
In C# 5, that has changed. The loop variable is considered new with each iteration, declared inside each iteration. Now it's more like
Code:
foreach (var temp in list)
{
var item = temp;And the reason this was changed between C# 4 and 5 was because of closures. People, and apparently a lot of them, were closing over the loop variable inside the loop and then doing evaluations of those closures outside the loop and were getting unexpected results. Closures close over the variables, not values, so what they were finding was at the end of it all, they had basically a bunch of closures that produced the same output because they were all referencing the same variable that would obviously hold the same value.
So for C# 5, they changed it so that people would see their programs work as they expected. The caveat, of course, is that if anyone was actually relying upon the previous behavior, it just broke. But at least it's a breaking change that makes sense.
In Python, apparently between 2 and 3 they decided to change division semantics between integers. In Python 2.x, it uses the same integer math you are accustomed to if you use languages like C#, Java, etc.
Code:
x = 2
y = 3
z = x / y
print zIt prints 0.
In Python 3.x, they decided to have it perform floating point math, which changes the output.
Code:
x = 2
y = 3
z = x / y
print(z) # also have to change this from aboveAnd you get 0.66666...
Frustrating. Now people that were actually relying upon integer division (think midpoint finding, just for one use case) have to go and fix who knows how many places inside their code.
Ufffff, making a Dungeon Generator, what the hell have I gotten myself into. I don't know why, but somehow I thought this would be way simpler. I think I'm gonna forego my path based digger and just partition it with BSP, dump in rooms and connect them.
It's fun to see how many different approaches there are though. Anybody have a decent implementation of a dungeon layout generator with connected rooms? Or any pointers on what I should focus on to get a layout with properly connected rooms?
It's fun to see how many different approaches there are though. Anybody have a decent implementation of a dungeon layout generator with connected rooms? Or any pointers on what I should focus on to get a layout with properly connected rooms?
Hey guys, I need some tips from you.
When I code in C++, I have a bad habit of passing entire arrays/vectors/whatevers instead of using pointers. I realize this is poor form and I want to correct it, but I'm having some trouble. Mind checking this out and helping me? Thanks!
I'm reading in lines of data from an open text file (which is what the variable "f" is), then I want to put it into an array of nodes. I've included my Node class I created. I'd appreciate any tips on how to build that class better too: am I using too many member functions? is my use of public/private ideal? Really appreciate it.
When I try to check to see the data (cout<<nodes[counter]->get_id()<<endl
I get this instead of the value: -842150451
I think that's the memory location instead of the actual data, but I'm not sure what I'm doing wrong. I really appreciate it, thanks!
When I code in C++, I have a bad habit of passing entire arrays/vectors/whatevers instead of using pointers. I realize this is poor form and I want to correct it, but I'm having some trouble. Mind checking this out and helping me? Thanks!
I'm reading in lines of data from an open text file (which is what the variable "f" is), then I want to put it into an array of nodes. I've included my Node class I created. I'd appreciate any tips on how to build that class better too: am I using too many member functions? is my use of public/private ideal? Really appreciate it.
Code:
class Node{
public:
void set_name (string _name) {_name = _name;}
void set_id (int _id) {_id = _id;}
void set_x_cord (int _x_cord) {_x_cord = _x_cord;}
void set_y_cord (int _y_cord) {_y_cord = _y_cord;}
string get_name() {return _name;}
int get_id() {return _id;}
int get_x_cord() {return _x_cord;}
int get_y_cord() {return _y_cord;}
private:
string _name;
int _id, _x_cord, _y_cord;
};
int main (){
int counter = 0;
Node* nodes[84];
while (f) {
Node* ptr = new Node;
f >> id;
ptr->set_id(id);
f >> x_cord;
ptr->set_x_cord(x_cord);
f >> y_cord;
ptr->set_y_cord(y_cord);
f >> name;
ptr->set_name(name);
nodes[counter] = ptr;
counter++;
}When I try to check to see the data (cout<<nodes[counter]->get_id()<<endl
I get this instead of the value: -842150451I think that's the memory location instead of the actual data, but I'm not sure what I'm doing wrong. I really appreciate it, thanks!
Hey guys, I need some tips from you.
When I code in C++, I have a bad habit of passing entire arrays/vectors/whatevers instead of using pointers. I realize this is poor form and I want to correct it, but I'm having some trouble. Mind checking this out and helping me? Thanks!
I'm reading in lines of data from an open text file (which is what the variable "f" is), then I want to put it into an array of nodes. I've included my Node class I created. I'd appreciate any tips on how to build that class better too: am I using too many member functions? is my use of public/private ideal? Really appreciate it.
Code:class Node{ public: void set_name (string _name) {_name = _name;} void set_id (int _id) {_id = _id;} void set_x_cord (int _x_cord) {_x_cord = _x_cord;} void set_y_cord (int _y_cord) {_y_cord = _y_cord;} string get_name() {return _name;} int get_id() {return _id;} int get_x_cord() {return _x_cord;} int get_y_cord() {return _y_cord;} private: string _name; int _id, _x_cord, _y_cord; }; int main (){ int counter = 0; Node* nodes[84]; while (f) { Node* ptr = new Node; f >> id; ptr->set_id(id); f >> x_cord; ptr->set_x_cord(x_cord); f >> y_cord; ptr->set_y_cord(y_cord); f >> name; ptr->set_name(name); nodes[counter] = ptr; counter++; }
When I try to check to see the data (cout<<nodes[counter]->get_id()<<endl
I think that's the memory location instead of the actual data, but I'm not sure what I'm doing wrong. I really appreciate it, thanks!
Uhh... so all the parameters in Node's methods have the same name as your member variables. You're just assigning the passed in values to itself and never assigning the members of the class.
Additionally, I see that you're prefixing all the member variables with an underscore, so DO NOT add this prefix to anything else. There are a few rules you want to follow when passing parameters around.
1. Is it a built in type, then pass by value. Otherwise pass by reference.
2. Am I modifying this parameter in the function? If not, it should be const.
just the first time as it reads the data from the file. after that, the values within the node won't change. you're suggesting creating a new class called "coord" that holds 2 ints in it, and use that within the Node class?
No, I'm suggesting replacing set_x_coord and set_y_coord with set_xy_coords( int const x, int const y ).
If nothing will change with the Node class, you could always just make a constructor that takes name, id, x, and y and have no setter functions.
Thanks, Lathentar. I'm taking all your suggestions and cleaning up my code.
2&3) I've since changed my code to look like this:
Thanks again.
1) Because I'm passing built in types (strings, ints), I'm passing the values. But if I were to pass an entire Node, I'd use a reference. Right?
2&3) I've since changed my code to look like this:
Code:
//in Node:
public:
Node(string const name, int const id, int const x_cord, int const y_cord) {
_name = name;
_id = id;
_x_cord = x_cord;
_y_cord = y_cord;
}
//in main:
Node* ptr = new Node(name, id, x_cord, y_cord);Thanks again.
I'm having some problems with arrays and lists in VisualBasic.
So, I have Array A and B, the dimension is given by the user (by and InputBox), and then they show in a Listbox (one for A and one for B).
Now, I want to arrange them (like, from greater to smaller) and then erase the content on List A and List B, and write the new sequences of numbers, so I do this:
And it work, but only for List A, not List B... At least, it doesn't show. The numbers in List A are sorted correctly, but in List B they are showed in the order they were inserted.
I tried separating the For that does the sorting and the For that adds the numbers to the list, but it didn't work, any ideas?
(Sorry for italian words in the code)
So, I have Array A and B, the dimension is given by the user (by and InputBox), and then they show in a Listbox (one for A and one for B).
Now, I want to arrange them (like, from greater to smaller) and then erase the content on List A and List B, and write the new sequences of numbers, so I do this:
Code:
Private Sub CmdOrdinaAB_Click(sender As System.Object, e As System.EventArgs) Handles CmdOrdinaAB.Click
ListBox1.Items.Clear()
ListBox2.Items.Clear()
For Indice = 0 To Dimensione - 1
For JIndiceOrdinamento = Indice + 1 To Dimensione
If A(Indice) > A(JIndiceOrdinamento) Then
Temp = A(Indice)
A(Indice) = A(JIndiceOrdinamento)
A(JIndiceOrdinamento) = Temp
End If
If B(Indice) = B(JIndiceOrdinamento) Then
Temp = B(Indice)
B(Indice) = B(JIndiceOrdinamento)
B(JIndiceOrdinamento) = Temp
End If
Next JIndiceOrdinamento
Next Indice
For Indice = 0 To Dimensione
ListBox1.Items.Add(A(Indice))
ListBox2.Items.Add(B(Indice))
Next Indice
MsgBox("Fine caricamento", 0, "Fine")
CmdCreaC.Enabled = True
End Sub
End ClassAnd it work, but only for List A, not List B... At least, it doesn't show. The numbers in List A are sorted correctly, but in List B they are showed in the order they were inserted.
I tried separating the For that does the sorting and the For that adds the numbers to the list, but it didn't work, any ideas?
(Sorry for italian words in the code
)The Last Wizard
Member
How important is math for programming, like calculus and higher?
It's domain knowledge. So it matters if you do programming in a domain where it's useful. For example, trig and linear algebra are super useful in game programming. Any type of numerical analysis and signal processing are going to be basically impossible without calculus.
We wrote an application at work to draft a ship using several gps signals, which required a ton of higher level math.
Building a website won't require calculus. Writing an inventory system won't require calculus.
Logic is important.
If you just want to code, math isn't so important. But if you want to develop and engineer proper software, math is essential.
I'm having some problems with arrays and lists in VisualBasic.
So, I have Array A and B, the dimension is given by the user (by and InputBox), and then they show in a Listbox (one for A and one for B).
Now, I want to arrange them (like, from greater to smaller) and then erase the content on List A and List B, and write the new sequences of numbers, so I do this:
Code:Private Sub CmdOrdinaAB_Click(sender As System.Object, e As System.EventArgs) Handles CmdOrdinaAB.Click ListBox1.Items.Clear() ListBox2.Items.Clear() For Indice = 0 To Dimensione - 1 For JIndiceOrdinamento = Indice + 1 To Dimensione If A(Indice) > A(JIndiceOrdinamento) Then Temp = A(Indice) A(Indice) = A(JIndiceOrdinamento) A(JIndiceOrdinamento) = Temp End If If B(Indice) = B(JIndiceOrdinamento) Then Temp = B(Indice) B(Indice) = B(JIndiceOrdinamento) B(JIndiceOrdinamento) = Temp End If Next JIndiceOrdinamento Next Indice For Indice = 0 To Dimensione ListBox1.Items.Add(A(Indice)) ListBox2.Items.Add(B(Indice)) Next Indice MsgBox("Fine caricamento", 0, "Fine") CmdCreaC.Enabled = True End Sub End Class
And it work, but only for List A, not List B... At least, it doesn't show. The numbers in List A are sorted correctly, but in List B they are showed in the order they were inserted.
I tried separating the For that does the sorting and the For that adds the numbers to the list, but it didn't work, any ideas?
(Sorry for italian words in the code
Code:
If B(Indice) = B(JIndiceOrdinamento) Thenshouldn't that be > ?
The Last Wizard
Member
The Tofunator
Member
I felt my calculus class was worthwhile, in the context of game programming. You learn about the relationships between position, velocity and acceleration. And how to for example, determine a jump acceleration if you want to be able to jump onto platforms 200 pixels off the ground. (although realistically I don't think many people do it that way. Trial and error is more fun. And usually the physics come before the levels)
TheFeedingHand
Member
Arrays are probably a little bit more efficient but that's about it. Vectors have pretty much any built-in operation you would need in an array.
You mean new[]?
If your compiler supports it, there's std::array now. Sometimes it's more natural to have a fixed-sized container, and it seems to be more efficient than std::vector. It doesn't seem worth it to use raw arrays though, unless you really need that extra performance.
smokeandmirrors
Banned
On my machine it is quite negligible:
http://i.imgur.com/Xmy9ZRT.png
Round 2:
http://i.imgur.com/VsUJloB.png
Reading from an external file filled with 2^20 integers. The code I'm using is for a class project so I don't want to post it right now just in case.
Vectors are θ(1) for access and insertion like normal arrays, and searching, like arrays is θ
. The only hit you'll get is the amortized cost of having to dynamically resize the array which will require θ(1) * θ time. (or θ)CrudeDiatribe
Member
At most schools, calculus is a pre-requisite to unlock of the math courses you're more likely to use/need in the real world (linear algebra, discrete math, number theory, graph theory). The math departments use it as a filter for competency rather than because of any overlap (there isn't any).
smokeandmirrors
Banned
Oh I know. I need to deal with sorting and deleting and such and i'm going to use both and I'll post results.
My point: unless you're going to be needing utmost efficiency vectors should be more than fine to use.
edit: even so, after multiple tests I still get .22ish seconds for reading and array insertion and .25ish for reading an vector insertion. I assume you'd still get a small hit when you're manually defining dynamic arrays so it really doesn't make a difference at all. your push_back() operation is basically going to be the same as copying to a larger array (as it's pretty much doing just that).
Is there any reason why modulo is intentionally not defined for arguments that aren't powers of two in VHDL? I'm talking IEEE.NUMERIC_STD and IEEE.STD_LOGIC_UNSIGNED. Instead I'm having to create trivial local signals to keep track of whenever another local signal hits the the divisor, but that's so theoretically simple I feel like the synthesiser should be able to do that itself so I didn't have to care. It's not like it's even close to as complicated as division either, modulo results in nice, usually small, natural numbers.
Because the modulo-2 is very cheap in terms of FPGA area I'd guess. I'm no expert on how synthesizing-algorithms are designed, but they probably don't support powers other than two for a reason.
Now that you mention it, most things you can write in VHDL would turn into a very small amount of logic gates and wires after optimisation, or at least a constant and predictable amount of them. The synthesising tool also did say something about allowing division and modulo by numbers that aren't powers of two as long as both are constant, and while that's worthless, it ties into the idea of restricting the number of things an expression can turn into to a predictable number depending on the size of the vector.
Celcius
°Temp. member
Just for fun I'm writing a quick multi-threaded java program to benchmark your cpu by computing all the prime numbers up to 200,000. The only problem occurs at the very end of the program where I try to show the prime numbers that were computed.
If you take out that very last for-loop inside the main method then the output shows normal. (shows the computation time but just doesn't show any of the prime numbers)
It seems like the output buffer gets overridden or something when I try to get each thread to print out its "primes" vector. I've also tried making the "primes" vector static so that it would be shared between all the threads and then just show that one vector, but it looks even weirder. Any ideas?
Code:
//Multi-threaded edition of benchmark program that calculates all the prime numbers less than 200,000
//a prime number is only divisible by 1 and itself
import java.util.Vector;
import java.io.*;
public class PrimesMT
{
public static void main(String[] args)
{
int cpuCores = Runtime.getRuntime().availableProcessors(); //determine how many processors are installed
try
{
int numThreads=0; //the number of threads to use
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
do
{
System.out.print("Your computer has "+cpuCores+" processors. How many would you like to use? ");
numThreads = Integer.parseInt(br.readLine()); //get the user's input
}while((numThreads<1)||(numThreads>cpuCores));
long startTime = System.currentTimeMillis(); //the timestamp when the calculation started
splitThread[] splitThreads = new splitThread[numThreads];
for (int h = 0; h < numThreads; h++) // create the threads
{
splitThreads[h] = new splitThread(h, numThreads);
}
for(int i = 0; i < numThreads; i++) // start the threads
{
splitThreads[i].start();
}
for(int i = 0; i < numThreads; i++) //halt main program until all threads finish calculations
{
try
{
splitThreads[i].join();
}
catch(Exception e)
{
System.out.println(e);
}
}
long stopTime = System.currentTimeMillis(); //the timestamp when the calculation stopped
long elapsed = ((stopTime - startTime) / 1000); //how long in seconds the calculation took
if (elapsed == 0) //if it took less than one second
{
elapsed = (stopTime - startTime); //how long in milliseconds the calculation took
System.out.println("That took ."+elapsed+" seconds.");
}
else //if it took longer than one second
{
int minutes = (int)elapsed / 60; //the minutes part of time elapsed
int seconds = (int)elapsed % 60; //the seconds part of time elapsed
System.out.println("That took "+minutes+" minute(s) and "+seconds+" second(s).");
}
System.out.println("The prime numbers computed were:"); //display the prime numbers computed
for(int i=0; i<numThreads-1; i++)
{
System.out.println(splitThreads[i].getName()+" computed: "+splitThreads[i].primes);
}
br.close();
}
catch(IOException ioe)
{
System.exit(0);
}
}
}
class splitThread extends Thread //this is the code for the threads to execute
{
Thread t2;
int iterations = 200000; //calculate all the primes up to this number
double iden; //thread id
double numbThreads; //total number of threads to use
Vector<Integer> primes = new Vector<Integer>(); //arraylist to hold the discovered primes
splitThread(int id, int nThreads) // id number, number of threads that will be created
{
iden = id;
numbThreads = nThreads;
t2 = new Thread(this, Integer.toString(id)); // Create a new thread
t2.setName("splitThread_"+Integer.toString(id));
System.out.println(t2.getName() + " created.");
}
public void run() // This is the entry point for the splitThreads.
{
try
{
//System.out.println(t2.getName()+" has launched!");
int minRange = (int)((iden/numbThreads)*200000)+1; //this thread should check for primes starting with this number
int maxRange = (int)(((iden+1)/numbThreads)*200000); //this thread should check for primes stopping with this number
boolean divByOthers = false; //if the number is divisible by something other than 1 or itself
System.out.println(t2.getName()+" is calculating primes from "+minRange+" to "+maxRange);//debug statement
for(int i=minRange; i<maxRange; i++) //check for primes
{
for(int y=(i-1); y>1; y--)
{
if(i%y==0)
divByOthers=true;
}
if(divByOthers==false)
{
if(i!=1)
primes.add(i);
//System.out.println("Prime number "+i+" discovered.");
}
divByOthers=false;
}
/*if(true) //show the discovered primes - don't do it like this because the threads are overwriting each other's info
{
System.out.println("The prime numbers discovered are:");
System.out.print(primes);
}*/
}
catch (Exception e)//InterruptedException e)
{
System.out.println("splitThread "+t2.getName()+" interrupted.");
}
}
}It seems like the output buffer gets overridden or something when I try to get each thread to print out its "primes" vector. I've also tried making the "primes" vector static so that it would be shared between all the threads and then just show that one vector, but it looks even weirder. Any ideas?
On my machine it is quite negligible:
http://i.imgur.com/Xmy9ZRT.png
Round 2:
http://i.imgur.com/VsUJloB.png
Reading from an external file filled with 2^20 integers. The code I'm using is for a class project so I don't want to post it right now just in case.
Vectors are θ(1) for access and insertion like normal arrays, and searching, like arrays is θ
They should be identical.
EDIT: Oh, well, perhaps I'll find or create an example so you don't have to.