Codeacious
Banned
I dunno, make is pretty quick about that part when I rebuild the Linux kernel. How large are you talking?
-
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
Ehh... I feel relational calculus would fundamentally fly in the face of functional type systems. Not that you're wrong. Just my initial impressions.
Off the type of my head, you'd scan the input string and look at the final character in the string. If it isn't a exclamation mark or question mark, just spit the string back at the user. If its an exclamation, say wow. And if it ends in a question mark then you then you can go ahead and check the number of blank spaces in the string to see what you should do. Do you have anything written so far that you want us to look at?
Well, I suppose a better word would be "declarative". Like, you're not at all specifying how something is to be done, but what you want.
Certainly. Lisp is probably the closest thing I've seen to it. But DB's are so much more unstructured. It's kinda crazy.
cpp_is_king
Member
Just curious. Used LINQ before?
Never, haven't even heard of it. Looking it up it sounds intriguing. So this is for querying data types native to a language?
cpp_is_king
Member
It's for blowing your mind.
Imagine you've got a std::vector of structs in c++, and you run a "database query" on that vector. That's what linq is.
C# language feature
You can take a randrom collection and just query for subsets that meet arbitrary criteria. You can group, join, order, intersect, just like a relational database
That's the only way to LINQ. I only write vanilla sql when in management studio.
I also prefer lambdas, which is just a different flavor of LINQ.
Lambdas are another thing I need more experience with. The past 3 years I've been put on projects where the go to solution is throw a regex at it. Ugh... I think I've had lifetime of those by now, but this is probably just the tip of the iceberg.
I swear they are impossible to come back to and read.
I swear they are impossible to come back to and read.
Divide the problem... that's the best solution.
You need to be able to
- print a string
- read user input into a string
- concatenate strings
and define functions that
- take a string and return its last char (or better, last non-white one)
- take a string and return the number of spaces in it
Once you've done this, it's a matter of building something with those blocks.
Is there something above that gives you problems?
For the rest, I suggest you write all needed steps on a sheet of paper. Imagine you're asking a child to perform a task, how would you describe each step?
SQL is different in that it's declarative. You say what you want to happen but not how it must happen. Instead of: "make a new empty list. now loop over all the things and put into this list all the things that have this property" you just say: "I want all the things that have this property".
Which is all very well until you learn saying what you want to happen this way instead of that way makes it faster and then you need to know what's going on behind the scenes anyway :'(
Which is all very well until you learn saying what you want to happen this way instead of that way makes it faster and then you need to know what's going on behind the scenes anyway :'(
runningjoke
Member
I don't have any real advice but I feel your pain. I work for a small company in NL and we're having a hard time finding PHP devs. We've tried recruiters in the past but they want too much money and we weren't really happy with the people they brought in. Response to newspaper ads, twitter, our own website etc is too low. I think we're going to try stackoverflow.
Thanks anyway, success finding somebody.
deltatheta
Member
That's a big assignment. Seems like you're getting overwhelmed. Take it a step at a time.
Start out by writing a program that reads a line of text and always responds the same way e.g. "That's interesting."). Then take each requirement, one at a time, and integrate it into your program, testing as you go.
Can somebody help me with why this program runs so slow? The I am doing an operation n times and each operation does n operations, so it should be O(n^2), but it is acting very slow at not very large Ns. In reality, it's closer to the summation formula. When n is 1, the inner function does 1 operation. Now n is 2 and the inner function does 2 operations., and so on. It's closer to (n(n+1))/2, but that is also O(n^2). Here's the code. When I enter 100, my computer kicks up the fans and starts crunching hard. You can comment out the print line right after the solution = getNextSolution() line in main. With larger Ns, the strings get so long that the console may not print them properly. I know keeping an array of my previous answers would make it faster, but this seems to be running really slow regardless.
For those curious, it generates the Look and Say Sequence. This is the result if you enter 10.
Code:
public class LookAndSay {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int num = 0;
do{
System.out.println("Enter the number of solutions you want to the pattern: ");
num = input.nextInt();
String solution = "1";
for (int i = 0; i < num; i++){
System.out.println(solution);
solution = getNextSolution(solution);
}
} while(num >= 0);
}
public static String getNextSolution(String input){
String solution = "";
if (input.length() == 0)
return input;
int count = 1;
for (int i = 0; i < input.length(); i++){
if (i + 1 != input.length()){
if (input.charAt(i) == input.charAt(i+1)){
count++;
}
else{
solution = solution + count + input.charAt(i);
count = 1;
}
}
else{
solution = solution + count + input.charAt(i);
return solution;
}
}
return solution;
}
}For those curious, it generates the Look and Say Sequence. This is the result if you enter 10.
Code:
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211cpp_is_king
Member
Each string operation is doing a copy and they're getting really long. Combined with the O(n^2) you're doing 3-4 massive string copies and memory allocations thousands of times.
Try using a stringbuilder class and new'ing it just once but calling Clear() at the top of each iteration
I see how that could be an issue. I just realized something though, and it should have been obvious to me. The strings are not getting longer linearly. In the worst case scenario, the string doubles in length from one solution to the next. This scenario never truly happens (except from 1 to 11), but the strings are growing in length exponentially. So I guess it would make sense that it is so slow. Here's an example of the worst case scenario, it wouldn't happen but it is an example:
I have string 123123123123123.
The solution to this string is:
111213111213111213111213111213. This string is twice as long. So if every case was the worst case, it would be 2^N, which is super slow.
Here is the solution for when you enter 20, for example:
Code:
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211Yes, it's a difficult problem, because the complexity, to get normally the n-th term of the sequence starting with a p-length chain is something like O(p x 1.3036^n). Anything with such a complexity is bound to explode for small values of n (p doesn't matter much).
String copies and allocation aren't helping, but that won't solve everything, since it won't change the complexity even if you do this more efficiently.
It's a hard problem, but it can be coded more efficiently. There's an Euler Project Problem on this Conway sequence, where they ask you the number of 1, 2 and 3 in the... billionth (10^12) term in the list ^_^
https://projecteuler.net/problem=419
You can see there that just starting with "1", the 40th in the sequence is already about 63000 characters long...
The 100th term shoud be a string over a terabyte long, not doable at all with the "normal" algorithm (and probably not displayable in a reasonable time).
cpp_is_king
Member
In a sense it will change the complexity, because the only significant operation being performed is the memory allocation, which is proportional to the length of the allocation. So it's could be said to be like O(n^3) or worse.
Change it to a StringBuilder will help, but best would be just allocating one huge buffer up front
Edit: or just a big pre-allocated char array, no needto do string operations if you're manipulating 1 character at a time
Yes, you're right, in the current state, it keeps re-allocating and copying string parts, and that increase the complexity...
But at the end, there's no way he can compute the 100th string*, anyway. It's about 10^13-10^14 operations, and would take nearly a terabyte, thus the operations will be I/O bounded because you'll need to use the HDD.
* at least by applying the rule to a string... If people are interested into some theory behind this, I found this link useful:
http://www.se16.info/mhi/Part1.htm
It allows to compute the number of 1, 2 and 3 in the n-th word by computing the n-th power of a 92x92 matrix, which can be done quite efficiently, if you want to solve the above Euler Project problem...
It also reduce the storage by one order of magnitude, should you want to compute the string, and I suspect you can do far better by factorizing again the parts.
Well guys i wrote the code, i will put it here to see if you guys have any feedback.
Code:
import java.util.Scanner;
public class ComputerFriend {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner console = new Scanner(System.in);
System.out.println("Please enter you statement, question, exclamation, or \"quit\" to quit.");
String input;
input = console.nextLine();
char last;
int count;
int length;
while (!input.equals("quit")) {
length = input.length();
if (length == 0) last = ' ';
else last = input.charAt(input.length() - 1);
count = 0;
if (last == '?') {
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == ' ' ) count++;
}
if ((count % 2) == 0) System.out.println("Yes");
else System.out.println("No");
} else if (last == '!') {
System.out.println("Wow!");
} else {
System.out.println("You always say \"" + input + "\".");
}
System.out.println("Please enter you statement, question, exclamation, or \"quit\" to quit.");
input = console.nextLine();
}
console.close();
}
}I rewrote it in C using a character array, and it does run a bit better. It was able to compute the 50th term of the sequence after some time, while the Java code turned my Macbook Pro into a hot iron and I had to give up eventually. I can't get GCC to allow me to reserve two character arrays with 10 million bytes. It will let me do a million, but not 10 million. Seems like a small limitation. Here's the code if you're interested:
Code:
#include "stdio.h"
void getNextSolution(char * solution, char * nextSolution);
void extendSolution( char * nextSolution, int count, char digit);
void copy(char * nextSolution, char * solution);
void clearSolution(char * solution);
int main()
{
char solution [1000000];
char nextSolution [1000000];
clearSolution(solution);
clearSolution(nextSolution);
int num = 0;
do{
solution[0] = '1';
printf("Enter the number of solutions you for the sequence: ");
scanf("%d", &num);
int i;
for (i = 0; i < num; i++){
printf("%s\n", solution);
getNextSolution(solution, nextSolution);
clearSolution(nextSolution);
}
clearSolution(solution);
clearSolution(nextSolution);
} while (num > 0);
}
void getNextSolution(char * solution, char * nextSolution)
{
int length = 0;
while (solution[length] != '\0')
length++;
//printf("The length is %d\n", length);
if (length == 0){
return;
}
int count = 1;
int i;
for (i = 0; i < length; i++){
if (i + 1 != length){
if (solution[i] == solution[i+1]){
//printf("here\n");
count++;
}
else{
//printf("there\n");
extendSolution(nextSolution, count, solution[i]);
count = 1;
}
}
else {
extendSolution(nextSolution, count, solution[i]);
copy(nextSolution, solution);
return;
}
}
copy(nextSolution, solution);
return;
}
void extendSolution( char* nextSolution, int count, char digit){
int i = 0;
while (nextSolution[i] != '\0'){
i++;
}
nextSolution[i++] = (char)(count + 48);
nextSolution[i++] = digit;
nextSolution[i] = '\0';
}
void copy(char * nextSolution, char * solution){
int i = 0;
while (nextSolution[i] != '\0'){
solution[i] = nextSolution[i];
i++;
}
solution[i+1] = '\0';
}
void clearSolution( char * solution){
int i;
for (i = 0; i < 1000000; i++)
solution[i] = '\0';
}cpp_is_king
Member
That's because static arrays are allocated on the stack. Generally stacks are 1MB or 4MB by default, depends on various factors.
In any case, a 1 million byte char array basically would eat your entire stack.
Try using a vector<char> instead. If you want arbitrarily large N, try writing directly to a file.
Do you know if there's any reason why the compiler won't allocate large tables on the heap instead of the stack when the size is perfectly known and big?
make sure to reserve the full buffer you need or it'll spend a lot of time resizing.
or just malloc a char array.
I'd say it's not that time-consuming... If I'm not mistaken, allocation is O(1) and storage size will double each time, so you may, in the absolute worse case, have to copy the equivalent of twice the final vector.
I just did a quick test using gprof, to fill a 10^8 char vector with basic values (index%256 casted to a char), it took my computer a bit more than 4s with reservation, and a bit less than 7s without reservation.
The difference will quickly not be noticeable if you do a couple computations for each char.
I'd be more worried by the difficulty to find a contiguous bloc of hundreds of megabytes... deque e.g. may be better than vectors for very long "strings".
I was thinking of practicing file I/O for it, but I just realized that it would be a lot of disk space usage. The memory size of the strings is approximately 1.3^N, where N is the term in the sequence. If I tried doing anything larger with files, it seems like it would grow ridiculously large. Like, eat up my entire hard drive large. Does the OS do any checks on that? What happens if I accidentally make a program try to write a 50 GB file? Not sure if it could with a 16 GB RAM limit.
The OS usually doesn't do checks unless you have limitations on the user account... The only limit may be the file system (a couple older ones, like FAT32, are limited to 4GB).
You may need to check your compiler options, and which functions you use to open the file, though, if you don't want to have issues with files over 4GB because of 32 bits limitations.
I've actually accidentally written a several-GB file in my Linux a couple years ago (a log file gone wrong), I just filled the hard drive until the system shut the computer down because disk space was unsufficient for the system...
Yes, you can, thankfully. Or you wouldn't be able to read a DVD with an older computer
I'm not even sure that CD images would fit in RAM in the first computer I owned with a CD)Writer...Did that cause serious problems with your Linux machine?The OS usually doesn't do checks unless you have limitations on the user account... The only limit may be the file system (a couple older ones, like FAT32, are limited to 4GB).
You may need to check your compiler options, and which functions you use to open the file, though, if you don't want to have issues with files over 4GB because of 32 bits limitations.
I've actually accidentally written a several-GB file in my Linux a couple years ago (a log file gone wrong), I just filled the hard drive until the system shut the computer down because disk space was unsufficient for the system...
Yes, you can, thankfully. Or you wouldn't be able to read a DVD with an older computer
Had to give that a try:
Code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
void
print_solution(const std::vector<char>& solution, unsigned int pos)
{
if ( pos > solution.size() ) {
std::cerr << "[print_solution] Error: trying to print out of range" << std::endl;
return;
}
std::ostream_iterator<char> iter(std::cout);
std::copy(solution.begin(), solution.begin()+pos, iter);
std::cout << std::endl;
}
void
append_char(std::vector<char>& solution, unsigned int& pos, char to_add)
{
if ( pos < solution.size() )
solution.at(pos) = to_add;
else
solution.push_back( to_add );
++pos;
}
void
append_solution(std::vector<char>& solution, unsigned int& pos, int count, char digit)
{
append_char( solution, pos, (char)( count + 48 ) );
append_char( solution, pos, digit );
}
void
swap_solutions(std::vector<char>& curr_sol, unsigned int& curr_pos, std::vector<char>& next_sol, unsigned int &next_pos)
{
std::swap(curr_sol, next_sol);
curr_pos = next_pos;
next_pos = 0;
}
void
next_solution(std::vector<char>& curr_sol, unsigned int& curr_pos, std::vector<char>& next_sol, unsigned int &next_pos)
{
int count = 1;
for (unsigned int i = 0; i < curr_pos; ++i ) {
if ( i < curr_pos -1 ) {
if ( curr_sol.at(i) == curr_sol.at(i+1) ) {
count++;
}
else {
append_solution(next_sol, next_pos, count, curr_sol.at(i));
count = 1;
}
}
else {
append_solution(next_sol, next_pos, count, curr_sol.at(i));
}
}
swap_solutions(curr_sol, curr_pos, next_sol, next_pos);
}
void
calculate_solutions(unsigned int num)
{
unsigned int curr_pos = 1, next_pos = 0;
std::vector<char> curr_sol(1000000), next_sol(1000000);
curr_sol.at(0) = '1';
for (unsigned int i = 0; i < num-1; ++i ) {
print_solution(curr_sol, curr_pos);
next_solution(curr_sol, curr_pos, next_sol, next_pos);
}
print_solution(curr_sol, curr_pos);
}
int main()
{
unsigned int num = 0;
std::cout << "Enter the number of solutions you for the sequence: " << std::flush;
while (std::cin >> num ){
calculate_solutions(num);
std::cout << "\nEnter the number of solutions you for the sequence: " << std::flush;
}
}I mainly wanted to avoid copying the values from one array to the other.
Comment out the print_solution() in the loop to only print the last solution.
cpp_is_king
Member
If it can't even fit on your disk, then surely it can't fit in memory
Welcome to the world of distributed storage. One of the "famous" old interview questions Google (I think it was G) used to ask is how would you sort a list of 10 billion integers.Anyway, unless you're using FAT32, there's no theoretical limit to the size of a file. Just because your file is 50GB doesn't mean it needs 50GB of memory. There's user mode and kernel mode caching and buffering going on so it doesn't ever need to ekep the whole file in memory at once.
cpp_is_king
Member
From the standard
This is the closest thing I can find, although 8.3.4.4 explicitly denotes the case of a runtime bound too big for automatic storage as undefined behavior. So basically, you could probably do it, but nobody wants to go out of their way to make undefined behavior work a specific way. It just works how it happens to work
This might be of interest to the C++ people here.
EA open sourced their STL.
https://github.com/electronicarts/EASTL
EA open sourced their STL.
https://github.com/electronicarts/EASTL
Not at all, but since I was using it remotely from my workplace (for work, I was studying DDoS from botnets), I've been unable to use it for the remainder of the day.
I'm just happy my ISP hasn't been angry becaused I actually launched by mistake a true DDoS against my personal machine...
I had just made a mistake on the mitigation parameter.
I couldn't use university machines as target because the firewalls were too efficient in dropping the packets. That's a kind of tcpdump that filled my hdd.
I see... Many thanks!
I'm currently rewriting my resume from scratch. Do you think I it's worth it to include technologies which I either
1) used just a few times, or
2) haven't used in a very long time (and can barely remember)
..just so I can say that I do have at least some experience with them?
I was thinking about splitting up the "Skills & Experiences" section into two separate subsections. "Skills" for stuff I actually know, and "Experiences" for things as described above.
1) used just a few times, or
2) haven't used in a very long time (and can barely remember)
..just so I can say that I do have at least some experience with them?
I was thinking about splitting up the "Skills & Experiences" section into two separate subsections. "Skills" for stuff I actually know, and "Experiences" for things as described above.
Pretty much what I did. My languages and technologies are categorized by which I relatively know the most about, no some about, no very little about and then there is a section with some of the stuff that I am most interested in learning.
Oh, this sounds like a good idea. Didn't think of that.
How did you name the different sections?
The heading for the area on the resume is "Languages and Technologies" and every section I have is a bullet point under it. Final bullet point is for technologies instead
Template is what I used and I filled it in with random stuff.
My general rule is this:
Only put languages/tech on your resume that you would feel confident answering questions about or solving problems with.
Anything else can be brought up in the interview if they ask for outside interests etc.
Purple Cheeto
Member
I'm trying to wrap my head around multithreading and I'm stumped.
I want to write a program with one producer and 2 consumers. The consumers should wait for the producer to produce data, and then the producer should wait for the consumers to finish. The consumers don't change the data, and should run in parallel.
This is what I have so far:
I have the producer thread sleep for a bit initially to make sure the consumers are waiting, but that's kind of ugly. But anyway, the producer seems to get notified only once and gets stuck in the loop at g_consumed.wait(lk). I can call notify_one() from the producer's wait loop, but then the consumers don't run in parallel. I've tried using a global mutex for everything, but it still gets locked and while it runs the consumers don't run in parallel. Also, from this http://en.cppreference.com/w/cpp/thread/condition_variable/notify_all it sounds like having separate mutex can be better.
Am I approaching this completely the wrong way? I tried finding examples, but most just have one consumer and usually the producer doesn't wait. Also, how can I avoid having that sleep_for at the beginning of the producer?
Is there any good website (or good book) that explains multithreading in C++11 for beginners?
I want to write a program with one producer and 2 consumers. The consumers should wait for the producer to produce data, and then the producer should wait for the consumers to finish. The consumers don't change the data, and should run in parallel.
This is what I have so far:
Code:
#include <thread>
#include <mutex>
#include <random>
#include <iostream>
#include <chrono>
#include <condition_variable>
std::condition_variable g_produced;
std::condition_variable g_consumed;
void producer(int& data, unsigned int n_consumers)
{
std::default_random_engine gen;
std::uniform_int_distribution<int> distr(1,20);
std::mutex mex;
std::this_thread::sleep_for(std::chrono::milliseconds(60));
while (true) {
{
std::lock_guard<std::mutex> lk(mex);
data = distr(gen);
std::cout << "[producer] produced " << data << std::endl;
}
g_produced.notify_all();
{
std::unique_lock<std::mutex> lk(mex);
for (unsigned int i = 0; i < n_consumers; ++i ) {
g_consumed.wait(lk);
std::cout << "[producer] got notified" << std::endl;
}
}
}
}
void consumer1(const int& data)
{
std::mutex mex;
while (true) {
{
std::unique_lock<std::mutex> lk(mex);
std::cout << "[consumer1] lock, waiting... " << std::endl;
g_produced.wait(lk);
std::cout << "[consumer1] data = " << data << std::endl;
}
g_consumed.notify_one();
}
}
void consumer2(const int& data)
{
std::mutex mex;
while (true) {
{
std::unique_lock<std::mutex> lk(mex);
std::cout << "[consumer2] lock, waiting... " << std::endl;
g_produced.wait(lk);
std::cout << "[consumer2] data = " << data << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(5));
}
g_consumed.notify_one();
}
}
int main()
{
int data = -1;
std::thread t1( producer, std::ref(data), 2);
std::thread t2( consumer1, std::cref(data) );
std::thread t3( consumer2, std::cref(data) );
t1.join();
t2.join();
t3.join();
}I have the producer thread sleep for a bit initially to make sure the consumers are waiting, but that's kind of ugly. But anyway, the producer seems to get notified only once and gets stuck in the loop at g_consumed.wait(lk). I can call notify_one() from the producer's wait loop, but then the consumers don't run in parallel. I've tried using a global mutex for everything, but it still gets locked and while it runs the consumers don't run in parallel. Also, from this http://en.cppreference.com/w/cpp/thread/condition_variable/notify_all it sounds like having separate mutex can be better.
cppreference said:
Am I approaching this completely the wrong way? I tried finding examples, but most just have one consumer and usually the producer doesn't wait. Also, how can I avoid having that sleep_for at the beginning of the producer?
Is there any good website (or good book) that explains multithreading in C++11 for beginners?