473,888 Members | 1,419 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

C++ vector algorithm

Hello,

This is OT, but since everybody here seems to have
a great knowledge of C++ I thought I'd ask.

I have this vector with n^2 elements (where n usually
is somewhere between 100 and 1000...)
My goal is to loop through these values (this is not
a real-time computation...) 5000 times or so, select a
random element from the vector and do some simple
operations on the most nearby neighbors - meaning on top,
under, left and right in the vector.

However there is this problem - when at the edge
of the vector, not all nearby neighbors can be computed
(since they are not in the vector).

This algorithm is based on a mathematical one which
states that if the are no nearby neighbors, then go
with 0 (zero) instead.

But, this stuff needs to be fast even though it's not
in real-time.

Here's what I've got so far:

S - the vector in question
S_size - total number of elements in S

for(int T = 0; T < T_repeat; T += 10) {
for(int l = 0; l < l_repeat; l += 10) {
for(int q = 0; q < q_repeat; q++) {
xrand = rand() % S_size + 1;
yrand = rand() % S_size + 1;

try {
U1 =(-S_values.at(xra nd).at(yrand)) *
S_values.at(xra nd).at(yrand);
U2 = S_values.at(xra nd).at(yrand) *
S_values.at(xra nd + 1).at(yrand);
} catch(...) {
cout << "borked" << endl;
}

/* Do some computing here */
dU = J * (float)(U2 - U1);
}
}
}

See the try/catch-stuff? Theres my problem.
Can I handle this is some nifty way by letting
the exception tell me what overflowed and at
what elements?

Its late at night here and I really should get to bed
- if there's something thats not clear here
I'd be pleased to answer.

Cheers.

-- Pelle
Jul 23 '05 #1
5 2181
S - the vector in question
S_size - total number of elements in S

for(int T = 0; T < T_repeat; T += 10) {
for(int l = 0; l < l_repeat; l += 10) {
for(int q = 0; q < q_repeat; q++) {
xrand = rand() % S_size + 1;
yrand = rand() % S_size + 1;


given an array (or std::vector)
int field[] = {1, 2, 3, 4};
it has 4 members ... sizeof(field)/sizeof(field[0])

if you use rand() % 4, possible numbers are in range [0..3], then you
add one more and use as index into you array, this will raise an
exception in case rand()%4 == 3

meine 10 cent

--daniel
Jul 23 '05 #2

"Pelle Beckman" <he******@chell o.se> wrote in message
news:TXD4e.299$ 184.89@amstwist 00...

I have this vector with n^2 elements (where n usually
is somewhere between 100 and 1000...)
My goal is to loop through these values (this is not
a real-time computation...) 5000 times or so, select a
random element from the vector and do some simple
operations on the most nearby neighbors - meaning on top,
under, left and right in the vector.

However there is this problem - when at the edge
of the vector, not all nearby neighbors can be computed
(since they are not in the vector).


Why not make your vector bigger, so if you want n = 100 you actually use n =
102, setting the extra elements to zero (as required by the math). Then as
you work with your 100 elements, they will all have defined neighbors. Then
you won't throw exceptions, and you won't have to waste time testing for
being near the edge.
Jul 23 '05 #3
"Pelle Beckman" <he******@chell o.se> wrote in message
news:TXD4e.299$ 184.89@amstwist 00...
Hello,

This is OT, but since everybody here seems to have
a great knowledge of C++ I thought I'd ask.

I have this vector with n^2 elements (where n usually
is somewhere between 100 and 1000...)
My goal is to loop through these values (this is not
a real-time computation...) 5000 times or so, select a
random element from the vector and do some simple
operations on the most nearby neighbors - meaning on top,
under, left and right in the vector.

However there is this problem - when at the edge
of the vector, not all nearby neighbors can be computed
(since they are not in the vector).

This algorithm is based on a mathematical one which
states that if the are no nearby neighbors, then go
with 0 (zero) instead.

But, this stuff needs to be fast even though it's not
in real-time.

Here's what I've got so far:

S - the vector in question
S_size - total number of elements in S

for(int T = 0; T < T_repeat; T += 10) {
for(int l = 0; l < l_repeat; l += 10) {
for(int q = 0; q < q_repeat; q++) {
xrand = rand() % S_size + 1;
yrand = rand() % S_size + 1;

try {
U1 =(-S_values.at(xra nd).at(yrand)) *
S_values.at(xra nd).at(yrand);
U2 = S_values.at(xra nd).at(yrand) *
S_values.at(xra nd + 1).at(yrand);
} catch(...) {
cout << "borked" << endl;
}

/* Do some computing here */
dU = J * (float)(U2 - U1);
}
}
}

See the try/catch-stuff? Theres my problem.
Can I handle this is some nifty way by letting
the exception tell me what overflowed and at
what elements?

Its late at night here and I really should get to bed
- if there's something thats not clear here
I'd be pleased to answer.

Cheers.

-- Pelle


If you want to go fast don't use "at" and don't use exceptions for what
amounts to flow control. There are two reasonable solutions:

1) put in artifical borders filled with zeros as someone else suggested, and
2) write special loops for use near the edges and corners.

I recently wrote some code which used method 2 and had to write 9 loops: top
left corner, top edge, top right corner, left edge, sweet spot in the
middle, right edge, lower right corner, bottom edge, and lower right corner.
It was a pain in the neck but turned out to be quite fast as well as
non-invasive. The loop for the middle part (where most of the data are) can
be coded without any runtime penalty for checking. The code at the corners
has lots of checking but only subtends a few elements.

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 23 '05 #4
Dana Cartwright skrev:
"Pelle Beckman" <he******@chell o.se> wrote in message
news:TXD4e.299$ 184.89@amstwist 00...
I have this vector with n^2 elements (where n usually
is somewhere between 100 and 1000...)
My goal is to loop through these values (this is not
a real-time computation...) 5000 times or so, select a
random element from the vector and do some simple
operations on the most nearby neighbors - meaning on top,
under, left and right in the vector.

However there is this problem - when at the edge
of the vector, not all nearby neighbors can be computed
(since they are not in the vector).

Why not make your vector bigger, so if you want n = 100 you actually use n =
102, setting the extra elements to zero (as required by the math). Then as
you work with your 100 elements, they will all have defined neighbors. Then
you won't throw exceptions, and you won't have to waste time testing for
being near the edge.


It's perfectly sane idea but since we're talking about
100000s of elements, a "border" would mean
1000s of "unnecessar y" elements which could require
a few megs memory req. extra depending on the
type of the vector.

-- Pelle
Jul 23 '05 #5
"Pelle Beckman" <he******@chell o.se> wrote in message
news:_lU4e.341$ 184.115@amstwis t00...
Dana Cartwright skrev:
"Pelle Beckman" <he******@chell o.se> wrote in message
news:TXD4e.299$ 184.89@amstwist 00...

Why not make your vector bigger, so if you want n = 100 you actually use
n = 102, setting the extra elements to zero (as required by the math).
Then as you work with your 100 elements, they will all have defined
neighbors. Then you won't throw exceptions, and you won't have to waste
time testing for being near the edge.


It's perfectly sane idea but since we're talking about
100000s of elements, a "border" would mean
1000s of "unnecessar y" elements which could require
a few megs memory req. extra depending on the
type of the vector.

-- Pelle


How big are your elements? If the maximum size is 1000 by 1000 (as I think
you said in your OP), that's only one million elements. Adding a border of
zeroes only adds about 4000, or 4%, storage overhead.

You said this needed to be fast. I'm just thinking that 4% memory overhead
is reasonable if you gain a lot of speed.

If your elements are large, then you could put them in memory that's
separate from the vector. The vector could be a vector of pointers into the
elements. Then, you need only create a single 'zero' element, because the
border pointers can (probably) all point at a single 'zero' element.
Jul 23 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

14
2750
by: Alex Vinokur | last post by:
Here is some function that detects if a vector contains only different elements bool vector_contains_only_different_elements (const vector<int>& v) { for (int i = 0; i < v.size(); i++) { if (count (v.begin() + i + 1, v.end(), v) >= 1) return false; } return true; }
6
3136
by: Matthias | last post by:
Hi, say I have a vector v1: std::vector<SomeType> v1; and I need a vector v2 of pointers to v1's elements: std::vector<SomeType*> v2;
12
3171
by: No Such Luck | last post by:
Hi All: I'm not sure if this is the right place to ask this question, but I couldn't find a more appropriate group. This is more of a theory question regarding an algorithm implemented in C, not necessarily a C language question. I'm trying to break up a vector into an arbitrary number of subvectors, equal (or as near to equal) in size as possible. My problem occurs when the vector is not evenly divisible by the number of subvectors...
3
2718
by: jackstah | last post by:
I've read before that subclassing off of std::vector is a bad idea because it's a concrete class. I understand, but there shouldnt be any issues with this. I just wanted to do a simple example in my project to combine templates and inheritance so that I would brush up on both. I have data that is mostly sorted, but there might be some flipflops here and there. Thus I've subclassed off of vector, and written a class that, given a...
8
1931
by: Michael | last post by:
Hi, I could use vector to get an array to random_shuffle it. Is it possible to define an array to random_shuffle it? I tried but it did not work. Can I use array instead of vector to use algorithm? Could you please help me out? Thanks. Michael
12
2196
by: mast2as | last post by:
Hi everyone I am working on some code that uses colors. Until recently this code used colors represented a tree floats (RGB format) but recently changed so colors are now defined as spectrum. The size of the vector went from 3 (RGB) to 151 (400 nm to 700 with a sample every 2nm). The variables are using a simple Vector class defined as follow: template<typename T, int Depth> class Vector
3
2178
by: Eric Lilja | last post by:
Hello, consider the following assignment and my code for it: /* Write a program that does the following: * Integer numbers shall be read from a textfile and stored in a std::vector. The name of the input file is to be given on the command line. * All negative values in the vector shall then be replaced with their positive counterpart, using the standard algorithm for_each.
10
8432
by: JDT | last post by:
Hi, Can someone provide me an example that uses std::max_element() (probablly the predicate version) to return the max "absolute" integer in a vector? Your help is much appreciated. Tony ps.
10
6088
by: arnuld | last post by:
WANTED: /* C++ Primer - 4/e * * Exercise: 9.26 * STATEMENT * Using the following definition of ia, copy ia into a vector and into a list. Use the single iterator form of erase to remove the elements with odd values from your list * and the even values from your vector.
42
4578
by: barcaroller | last post by:
In the boost::program_options tutorial, the author included the following code: cout << "Input files are: " << vm.as< vector<string() << "\n"; Basically, he is trying to print a vector of string, in one line. I could
0
9800
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11181
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10778
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10886
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10439
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9597
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5819
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
4245
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3252
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.